给定一个整型数组a[],计算最大连续子段和。
例子:
输入:(2, -8, 3, -2, 4, -10)
输出:5 连续子段为(3, -2, 4)
思路:
典型的动态规划问题。对于DP,我们要先找到状态,然后再找到递推关系。定义d[i]为以a[i]结尾的最大连续子段和,那么递推关系为:如果d[i - 1] > 0,d[i] = d[i - 1] + a[i];否则d[i] = a[i]。最后的结果为max{d[i], 0 <= i < n}。我们注意到递推式中d[i]只与d[i - 1]有关系,所以可以将O(n)的空间降为O(1)。
#include <iostream>
#include <vector>
using namespace std;
int MaxSum......
阅读全文