連續子數組的最大和，連續子數組

連續子數組的最大和，連續子數組

題目：輸入一個整形數組，數組裡有正數也有負數。組中連續的一個或多個整數組成一個子數組，每個子數組都有一個和。求所有子數組的和的最大值。要求時間復雜度為O(n)。

思路:當我們加上一個正數時，和會增加；當我們加上一個負數時，和會減少。如果當前得到的和是個負數，那麼這個和在接下來的累加中應該拋棄並重新清零，不然的話這個負數將會減少接下來的和，用一個變量記錄最大的和，最後返回即可。

 1 #include<stdio.h>
 2 #include "stdafx.h"
 3 
 4 bool g_InvalidInput = false;
 5 
 6 int FindGreatestSumOfSubArray(int *pData, int nLength)
 7 {
 8     if((pData == NULL) || (nLength <= 0))
 9     {
10         g_InvalidInput = true;
11         return 0;
12     }
13     
14     g_InvalidInput = false;
15     
16     int nCurSum = 0;
17     int nGreatestSum = 0x80000000;
18     for(int i = 0; i < nLength; ++i)
19     {
20         if(nCurSum <= 0)
21             nCurSum = pData[i];
22         else
23             nCurSum += pData[i];
24         
25         if(nCurSum > nGreatestSum)
26             nGreatestSum = nCurSum;
27     }
28     
29     return nGreatestSum;
30 }
31 
32 int main()
33 {
34     int data[] = {1, -2, 3, 10, -4, 7, 2, -5};
35     int nLength = sizeof(data)/ sizeof(int);
36     int result = FindGreatestSumOfSubArray(data, nLength);
37     bool expectedFlag = false;
38     if(expectedFlag == g_InvalidInput)
39         printf("%d", result);
40     else
41         printf("Failed");
42     return 0;
43 }