[LeetCode] Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

思路一：动态规划的思想。时间复杂度O(n),空间复杂度O(1)。给出《剑指offer》面试题31的代码，它不仅时空复杂度较好，而且还较好的处理了无效输入的情况。

　　　　如果参数为空指针、数组长度小于0的情况。此时返回0。为了区分子数组的最大值是0和无效输入这两种不同的请款。设置一个全局变量来标记是否输入无效。

　　　　动态规划三个步骤：

　　　　1. 定义状态：dp(i)表示最大总和子数组的结束位置是i

　　　　2. 定义初始状态：dp(0)=a[0]

　　　　3. 状态转移方程：dp[i] = max{dp(i-1)+a[i], a[i]}，表示如果i-1结尾的最大子数组和加上当前元素如果比当前元素小，那么以i结尾的最大子数组和就是其本身。

 1 bool g_InvalidInput = false;
 2 
 3 int FindGreatestSumOfSubArray(int *pData, int nLength) {
 4     if ((pData == NULL) || (nLength <= 0))
 5     {
 6         g_InvalidInput = true;
 7         return 0;
 8     }
 9 
10     g_InvalidInput = false;
11 
12     int nCurSum = 0;
13     int nGreatestSum = 0x80000000;
14     for (int i = 0; i < nLength; ++i) 
15     {
16         if (nCurSum <= 0) 
17             nCurSum = pData[i];
18         else
19             nCurSum += pData[i];
20 
21         if (nCurSum > nGreatestSum)
22             nGreatestSum = nCurSum;
23     }
24 
25     return nGreatestSum;
26 }

思路二：分治策略。时间复杂度O(nlgN),空间复杂度O(1)。

 1 class Solution {
 2 public:
 3     int maxSubArray(int A[], int n) {
 4     return maxSubArray(A, 0, n - 1);
 5 }
 6 
 7 int maxSubArray(int A[], int low, int high) {
 8     if (low == high) return A[low];
 9 
10     int mid = (low + high) /2;
11     int max_left_sum = maxSubArray(A, low, mid);
12     int max_right_sum = maxSubArray(A, mid + 1, high);
13 
14     int max_cross_leftsum = INT_MIN, cross_leftsum = 0;
15     for (int i = mid; i >= low; --i) {
16         cross_leftsum += A[i];
17         if (cross_leftsum > max_cross_leftsum)
18             max_cross_leftsum = cross_leftsum;
19     }
20 
21     int max_cross_rightsum = INT_MIN, cross_rightsum = 0;
22     for (int i = mid + 1; i <= high; ++i) {
23         cross_rightsum += A[i];
24         if (cross_rightsum > max_cross_rightsum)
25             max_cross_rightsum = cross_rightsum;
26     }
27 
28     int max_cross_sum = max_cross_leftsum + max_cross_rightsum;
29 
30     if (max_left_sum >= max_cross_sum && max_left_sum >= max_right_sum) {
31         return max_left_sum;
32     } else if (max_right_sum >= max_cross_sum && max_right_sum >= max_left_sum) {
33         return max_right_sum;
34     } else {
35         return max_cross_sum;
36     }
37 }
38 };

参考资料：

　　1. 《数据结构与算法分析C++描述》（第三版）　　人民邮电出版社　　2.43

　　2. 《算法导论》（第三版）　　机械工业出版社　　4.1

　　3. 《编程珠玑》（第二版）　　人民邮电出版社　　第8章

　　4. 《编程之美》　　电子工业出版社　　2.14

　　5. 《剑指offer》　　电子工业出版社　　面试题31