首页 > 代码库 > [LeetCode] Maximum Subarray
[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 bool g_InvalidInput = false; 2 3 int FindGreatestSumOfSubArray(int *pData, int nLength) { 4 if ((pData =http://www.mamicode.com/= 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 else19 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 };
[LeetCode] Maximum Subarray
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。