最大子数组和

浏览数：33 / 时间：2015年06月08日

题目描述

给定一个数组a[0,...,n-1],求其最大子数组(长度>=1)和

输入描述

第一行一个整数n(1<=n<=5000)，然后依次输入n个整数（每个整数范围[-5000, 5000]）

输出描述

输出一个整数表示最大子数组和

样例输入

5
1 -1 1 1 -1

样例输出



当然有搜索或者枚举等等，O(n)的算法可以用DP。

设sum[i]为以第i个元素结尾且和最大的连续子数组。
假设对于元素i，所有以它前面的元素结尾的子数组的长度都已经求得，那么以第i个元素结尾且和最大的连续子数组实际上，要么是以第i-1个元素结尾且和最大的连续子数组加上这个元素，要么是只包含第i个元素，即sum[i] = max(sum[i-1] + a[i], a[i])。
可以通过判断sum[i-1] + a[i]是否大于a[i]来做选择，而这实际上等价于判断sum[i-1]是否大于0。
由于每次运算只需要前一次的结果，因此并不需要像普通的动态规划那样保留之前所有的计算结果，只需要保留上一次的即可，因此算法的时间和空间复杂度都很小。

代码如下：

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6     int n, num;
 7     long sum, max;
 8     cin >> n;
 9     cin >> sum;
10     max = sum;
11     for (int i = 1; i < n; i++)
12     {
13         cin >> num;
14         if (sum > 0)
15             sum += num;
16         else
17             sum = num;
18         if (sum > max)
19             max = sum;
20     }
21 
22     cout << max;
23 
24     return 0;
25 }