首页 > 代码库 > 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.
如果当前的和小于0，则在后面的数加上现在的和只会比原来的数要小，故舍弃
DP的思路：
O(n)就是一维DP。
假设A(0, i)区间存在k，使得[k, i]区间是以i结尾区间的最大值，定义为Max[i]，当求取Max[i+1]时，
然后从左往右扫描，求取Max数字的最大值即为所求。
假设A(0, i)区间存在k，使得[k, i]区间是以i结尾区间的最大值，定义为Max[i]，当求取Max[i+1]时，
然后从左往右扫描，求取Max数字的最大值即为所求。
1 class Solution { 2 public: 3 int maxSubArray(int A[], int n) { 4 int ans = 0; 5 int maxsum = INT_MIN; 6 7 for (int i = 0; i < n; i++) 8 { 9 if (ans < 0)10 ans = 0;11 ans += A[i];12 maxsum = max(ans, maxsum);13 }14 return maxsum;15 }16 };
LeetCode - Maximum Subarray
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。