PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] 連續整數相乘，求乘積最大?

看板Prob_Solve (計算數學 Problem Solving)作者bleed1979 (十三)時間16年前 (2008/05/15 22:55)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串3/6 (看更多)

這方法比較笨而且慢關鍵在於開始乘的起點比如 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)