动态规划问题03_最大子段和

• 题目描述：
  给定由n个整数（包含负整数）组成的序列：a1、a2、a3……an，求该序列子段和的最大值。
• 输入：
  若干个整数
• 输出：
  子序列和的最大值

---

案例输入输出：

• Input:
  1 -3 7 8 -4 12 -10 6
• Output:
  23

---

#include<iostream>
using namespace std;

int a[128];
int n;
int MaxSum(){
    
    int sum = 0;
    int b = 0;
    for(int i=1; i<=n; i++){
    
        if(b>0){
    
            b += a[i];
        } else{
    
            b = a[i];
        }
        if(b>sum){
    
            sum = b;
        }
    }
    return sum;
}

int main()
{
    
    cin>>n;
    for(int i=1; i<=n; i++){
    
        cin>>a[i];
    }
    cout<<MaxSum()<<endl;
   return 0;
}