最大子段和

题目

出一个整数数组a(正负数都有)，如何找出一个连续子数组（可以一个都不取，那么结果为0），使得其中的和最大？
例如：-2,11,-4,13,-5,-2，和最大的子段为：11,-4,13。和为20。
输入
第1行：整数序列的长度N（2 <= N <= 50000)
第2 - N + 1行：N个整数（-10^9 <= A[i] <= 10^9）
输出
输出最大子段和。
输入示例
6
-2
11
-4
13
-5
-2
输出示例
20

代码

#include<iostream>
#include<algorithm>
using namespace std;
#define inf 0x7fffffff;
int MaxSum(int n, int a[])
{
  int sum = -inf;
 int b = 0;
  for (int i = 0; i < n; i++)
 {
  if (b > 0)
  b += a[i];
  else
      b = a[i];
  sum = max(b, sum);
  }
  return sum;
 }
 int main()
 {
  int n;
  cin >> n;
  int* a =new int[n];
  for (int i = 0; i < n; i++)
  {
  cin >> a[i];
  }
  cout << MaxSum(n, a);
  return 0;
}