作者bleed1979 (十三)
站內Prob_Solve
標題Re: [問題] 連續整數相乘，求乘積最大?
時間Thu May 15 22:54:57 2008
這方法比較笨而且慢
關鍵在於開始乘的起點
比如 0 0 1 2 3 -1 3 4 5 -2 1 來說好了
一開始begin當然是0
1.如果乘數為0 begin加1
2.如果乘數是正數 begin加1 並標明begin更動過
3.如果乘數是負數
第一次碰到負數
將之前的乘積丟到vector
第二次碰到負數
begin等於現在的index 再標明begin更動過
乘完負負得正的乘積加入vector中
4.如果begin沒被更動過 begin加1
5.最後找乘積最大者即可
/*****************************/
/* Problem 11059 */
/* Lang: C++ */
/* Author: Chien-Mao Chen */
/* Last Modified: 2008/05/15 */
/*****************************/
#include <iostream>
#include <vector>
using namespace std;
int main(void)
{
int n,cases=0;
char c;
while((c=cin.get())&&c!=EOF)
{
ungetc(c,stdin);
cin>>n;
vector<int> number;
number.clear();
int value;
for(int i=0; i<n; ++i)
{
cin>>value;
number.push_back(value);
}
cin.get();
vector<long long> product_list;
product_list.clear();
int begin=0;
long long product=-1;
while(begin<number.size())
{
while(begin<number.size()&&number[begin]==0) ++begin;
if(begin>=number.size()) break;
bool isNegative=false;
bool isBeginChanged=false;
product=0;
for(int i=begin; i<number.size(); ++i)
{
if(number[i]>0)
{
if(product==0) product=1;
product*=number[i];
if(!isBeginChanged)
{
++begin;
isBeginChanged=true;
}
}
else if(number[i]<0)
{
if(!isNegative)
{
product_list.push_back(product);
isNegative=true;
}
if(product==0) product=1;
product*=number[i];
if(isNegative)
{
isNegative=false;
product_list.push_back(product);
if(begin<i&&!isBeginChanged)
{
begin=i;
isBeginChanged=true;
}
}
}
else
break;
}
if(!isBeginChanged) ++begin;
product_list.push_back(product);
}
long long max_product;
if(product_list.size()>0)
{
max_product=product_list[0];
for(int i=1; i<product_list.size(); ++i)
if(max_product<product_list[i])
max_product=product_list[i];
if(max_product<0) max_product=0;
}
else
max_product=0;
if(max_product<0) max_product=0;
cout<<"Case #"<<++cases<<": The maximum product is
"<<max_product<<"."<<endl<<endl;
}
return 0;
}
※ 引述《polomoss (小澤)》之銘言：
: 希望大大給點想法，今天寫題目的時候卡住了~
: 講的越詳細越好~~
: 使用者給一串整數，要找出它"連續"，且乘積最大者
: 例如:
: 5 -2 1 -1 最大 5*-2*1*-1 = 20
: -1 2 5 最大 2*5 = 10
: 1 2 0 -3 -1 最大 -3*-1 = 3
: 大概是這樣~~
: 先謝謝了~
--
ACM's PARADISE
http://bleed1979.myweb.hinet.net/
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.116.16.70
※ 編輯: bleed1979 來自: 122.116.16.70 (05/15 23:04)