【面试题031】连续子数组的最大和

【面试题031】连续子数组的最大和

题目：

输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。

求所有子数组的和的最大值。要求时间复杂度为O(n)。

思路一：

枚举出数组的所有子数组并求出他们的和，最快也需要O(n^2)的时间，

思路二：

举例分析数组的规律，如果加上一个负数，那个先前的累加和势必会减少，把先前的累加和记下来，因为这个累加和是可能的最大值，

然后接着加上这个负数，举行累加，如果那一步出现累加和大于先前记录下来的累加和，更新最大值，最后的那个最大值就是答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

#include <iostream>

using namespace std;

bool g_InvalidInput = false;
int FindGreatestSumOfSubArray(int *pData, int nLength)
{
    if ((pData == NULL) || (nLength <= 0))
    {
        g_InvalidInput = true;
        return 0;
    }
    g_InvalidInput = false;

    int nCurSum = 0;
    int nGreatestSum = 0x80000000;
    for (int i = 0; i < nLength; ++i)
    {
        if (nCurSum <= 0)
        {
            nCurSum = pData[i];
        }
        else
        {
            nCurSum += pData[i];
        }
        if (nCurSum > nGreatestSum)
        {
            nGreatestSum = nCurSum;
        }
    }
    return nGreatestSum;
}

int main()
{
    int num[] = {1, -2, 3, 10, -4, 7, 2, -5};
    int length = sizeof(num) / sizeof(num[0]);
    cout << FindGreatestSumOfSubArray(num, length) << endl;
    return 0;
}

思路三：

应用动态规划，

如果f(i)表示以第i个数字结尾的子数组的最大和，0<=i<n。

如果i=0或者f(i-1)<=0,那么f(i) = pDate[i];

如果i!=0并且f(i-1)>0,那么f(i) = f(i-1) + pDate[i];