首页 > 代码库 > Maximum Subarray
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^3)时间复杂度，超时
1 public class Solution { 2 public int maxSubArray(int[] A) { 3 int maxValue = http://www.mamicode.com/0; 4 for(int i = 0; i < A.length; i++){ 5 for(int j = 0; j < A.length; j++){ 6 int sum = 0; 7 for(int k = i; k <= j; k++){ //计算sum 8 sum += A[k]; 9 }//for10 maxValue = http://www.mamicode.com/maxValue > sum ? maxValue : sum; //更新maxValue11 }//for12 }//for13 14 return maxValue;15 }16 }
思路二：
O(N^2)时间复杂度，超时，ps:c++实现一样超时
1 public class Solution { 2 public int maxSubArray(int[] A) { 3 int maxValue = http://www.mamicode.com/A[0]; 4 for(int i = 0; i < A.length; i++){ 5 int sum = A[i]; 6 for(int j = i + 1; j < A.length; j++){ 7 sum += A[j]; 8 maxValue = http://www.mamicode.com/maxValue > sum ? maxValue : sum; 9 }//for10 }//for11 12 return maxValue;13 }14 }
思路三：
DP，O(n)时间复杂度，可以AC
遍历数组，对于任意元素A[i]，只有两种可能，放到[k...i - 1]中，不放到[k...i - 1]中
1.放：此时sum,即连续子串的和为sum(A[k...i])
2.不放：此时sum,即连续子串的和为sum(A[i])
if(sum(A[k...i]) > sum(A[i])) 放A[i]，否则不放A[i],从A[i]开始计算sum
注意站在A[i]的角度去想
1 public class Solution { 2 public int maxSubArray(int[] A) { 3 int maxValue = http://www.mamicode.com/A[0]; 4 int sum = A[0]; 5 for(int i = 1; i < A.length; i++){ 6 int temp = sum + A[i]; 7 sum = temp > A[i] ? temp : A[i]; 8 maxValue = http://www.mamicode.com/maxValue > sum ? maxValue : sum; 9 }10 11 return maxValue;12 }13 }
思路四：分治法待续...
ps:相同代码，c++的时间确实要比java块很多
Maximum Subarray
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。