leetcode_question_53 Maximum Subarray

发布时间:2016-12-11 6:30:49 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"leetcode_question_53 Maximum Subarray",主要涉及到leetcode_question_53 Maximum Subarray方面的内容,对于leetcode_question_53 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. More practice: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle. dp: int maxSubArray(int A[], int n) { // Start typing your C/C++ solution below // DO NOT write int main() function int max = A[0]; int currentsum = A[0]; for(int i = 1; i < n; ++i){ if(currentsum < 0) currentsum = 0; currentsum += A[i]; if(currentsum > max) max = currentsum; } return max; } Divide and Conquer: int calmaxsubarr(int A[], int begin, int end){ if(begin == end) return A[begin]; int mid = (end-begin)/2 + begin; int left = calmaxsubarr(A, begin, mid); int right = calmaxsubarr(A, mid+1, end); int lefthalf = A[mid]; int tmp = A[mid]; for(int i = mid -1; i >= begin; i--){ tmp += A[i]; if(tmp > lefthalf) lefthalf = tmp; } int righthalf = A[mid+1]; tmp = A[mid+1]; for(int i = mid +2; i <= end; ++i){ tmp += A[i]; if(tmp > righthalf)righthalf = tmp; } int middle = lefthalf + righthalf; int res = left > right ? left : right; res = res > middle ? res : middle; return res; } int maxSubArray(int A[], int n) { // Start typing your C/C++ solution below // DO NOT write int main() function return calmaxsubarr(A, 0, n-1); }

上一篇:EXT 各种消息提示框
下一篇:Remove Duplicates from Sorted List II

相关文章

相关评论