最大連續子序列和

may

數值陣列-2,1,-3,4,-1,2,1,-5,4 的最大連續子序列的和是多少?

may

1. //動態規畫,若前一元素和大於0,則歸0
   
2. #include <bits/stdC++.h>
   
3. using namespace std;
   
4. int main(){
   
5.    int nums[]={-2,1,-3,-4,1,1,-1,5,-4};
   
6.    int max_sum;
   
7.    int sum=max_sum=0;//預設值
   
8.    int len_nums=sizeof(nums)/sizeof(nums[0]);
   
9.    for(int i=0;i<len_nums;i++){
   
10.      if(sum<0)
    
11.         sum=0;
    
12.      sum +=nums[i];   
    
13.       max_sum=max(sum,max_sum);
    
14.    }
    
15.    cout<<max_sum<<"\n";
    
16. 
    
17.    return 0;
    
18. }

複製代碼

may

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. string raw;
   
4. int n;
   
5. stringstream ss;
   
6. vector<int> data;
   
7. int sum=0;
   
8. int max_sum=0;
   
9. 
   
10. int main()
    
11. {
    
12.     cin.tie(0); cin.sync_with_stdio(0);
    
13.     getline(cin, raw);
    
14.     ss<<raw;
    
15.     while(ss>>n)
    
16.         data.push_back(n);//先把輸入的數列存到data
    
17.     for(int i: data){ //若sum<0,則歸0,求最大連續子序列的和
    
18.         if(sum<0)
    
19.             sum=0;
    
20.         sum+=i;
    
21.         max_sum=max(sum,max_sum);
    
22.     }
    
23.         //cout<<i<<" ";
    
24.     cout<<max_sum<<endl;
    
25. 
    
26.     return 0;
    
27. }

複製代碼