作者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)