连续子数组的最大和

一个数组中，既有正数，也有负数，计算出他的子数组和的最大值。

思路：
我们从头开始遍历数组，遍历到数组元素 arr[ i ] 时，连续的最大的和 可能为 max( dp[ i -1 ] ) + arr[ i ] ，也可能为 arr[ i ] ，做比较即可得出哪个更大，取最大值。时间复杂度为 n

#include <iostream>
using namespace std;

int GetMax(int a, int b)
{
    return a > b ? a : b;
}
int FindMaxSum(int a[],int N)
{
    int sum = a[0];
    int max = a[0];
    for (int i = 1; i < N; i++)
    {
        sum = GetMax(sum + a[i], a[i]);
        if (sum >= max)
            max = sum;
    }
    return max;
}

int main()
{
    int a[] = { 1, 4, -3, 6, 2 };
    int N = sizeof(a) / sizeof(a[0]);
    FindMaxSum(a, N);
    return 0;
}