Advertisement
ambition-xx

Maximum Subsequence Sum

Nov 13th, 2020 (edited)
111
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.49 KB | None | 0 0
  1. #include<iostream>
  2. using namespace std;
  3. const int MAXN = 10; //元素个数
  4. int a[MAXN] = {-10, 1, 2, 3, 4, -5, -23, 3, 7, -21};
  5.  
  6. int main(){
  7.     int thisSum = 0, maxSum = 0;
  8.     //时间复杂度:O(n)
  9.     for(int i = 0; i < MAXN; i++){
  10.         thisSum += a[i];
  11.         //如果发现更大的子段和,那么更新maxSum
  12.         if(thisSum > maxSum) maxSum = thisSum;
  13.         //如果当前子段和小于0,那么丢弃
  14.         if(thisSum < 0) thisSum = 0;
  15.     }
  16.     cout<<maxSum<<endl;
  17.     return 0;
  18. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement