随手小代码——最大子数组联机算法

请通过右侧公告中的“联系邮箱（wlsandwho@foxmail.com）”联系我

未经作者授权勿用于学术性引用。

未经作者授权勿用于商业出版、商业印刷、商业引用以及其他商业用途。　　　　　　　　　　　　　　　　

本文不定期修正完善，为保证内容正确，建议移步原文处阅读。 <--------总有一天我要自己做一个模板干掉这只土豆

本文链接：http://www.cnblogs.com/wlsandwho/p/4715119.html

耻辱墙：http://www.cnblogs.com/wlsandwho/p/4206472.html

=======================================================================

改进了一下，记录最大子数组的下标。

不知道是不是能用。

=======================================================================

 1 #include "stdafx.h"
 2 #include <intsafe.h>
 3 #include <iostream>
 4 
 5 using namespace std;
 6 
 7 
 8 int LinearFindMaxSubArray(int nArray[], int nLen, int& nMaxLeftIndex, int& nMaxRightIndex)
 9 {
10     int nMaxSum = 0;
11     int nSum = 0;
12 
13 
14     for (int nIndex = 0;nIndex < nLen;nIndex++)
15     {
16         nSum += nArray[nIndex];
17 
18         if (nSum > nMaxSum)
19         {
20             nMaxSum = nSum;
21 
22             nMaxRightIndex = nIndex;
23         }
24         else
25         if (nSum < 0)
26         {
27             nSum = 0;
28 
29             nMaxLeftIndex = nIndex + 1;
30         }
31     }
32 
33     return nMaxSum;
34 }
35 
36 
37 int main()
38 {
39     int nArr[16] = { 13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7 };
40 
41     int nMaxLeftIndex = 0;
42     int nMaxRightIndex = 0;
43     int nMaxSum = LinearFindMaxSubArray(nArr,16, nMaxLeftIndex, nMaxRightIndex);
44 
45     cout << "nArr[" << nMaxLeftIndex << "..." << nMaxRightIndex << "] = " << nMaxSum << endl;
46 
47 //     int nArr[10] = { -2, 11, -4, 13, -5, 2, -5, -3, 12, -9 };
48 // 
49 //     int nMaxLeftIndex = 0;
50 //     int nMaxRightIndex = 0;
51 //     int nMaxSum = LinearFindMaxSubArray(nArr, 9, nMaxLeftIndex, nMaxRightIndex);
52 // 
53 //     cout << "nArr[" << nMaxLeftIndex << "..." << nMaxRightIndex << "] = " << nMaxSum << endl;
54 
55     return 0;
56 }

=======================================================================

随手小代码——最大子数组 联机算法

随手小代码——最大子数组联机算法