首页 > 代码库 > leetcode 24th round
leetcode 24th round
public class Solution { public int maxSubArray(int[] A) { return totalMax(A, 0, A.length-1); } public int totalMax(int[] A, int low, int high) { if(low == high) { return A[low]; } int mid = (low+high)/2; int leftMax = totalMax(A, low, mid); int rightMax = totalMax(A, mid+1, high); int crossMax = MidMax(A, low, mid, high); if((leftMax > rightMax) && (leftMax > crossMax)) { return leftMax; } else if ((rightMax > leftMax) && (rightMax > crossMax)) { return rightMax; } else { return crossMax; } } public int MidMax(int[] A, int low, int mid, int high) { int left_sum = Integer.MIN_VALUE; int sum = 0; int left_ind = mid; for(int i = mid; i >= low; i--) { sum = sum + A[i]; if(sum > left_sum) { left_sum = sum; left_ind = i; } } int right_sum = Integer.MIN_VALUE; sum = 0; int right_ind = mid; for (int i = mid+1; i <= high; i++) { sum = sum + A[i]; if(sum > right_sum) { right_sum = sum; right_ind = i; } } return (left_sum + right_sum); }}
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.
这道题的解我没有想出来，但隐约觉得应该是dynamic programming
我为自己感到羞愧，这道题是算法书上的原题！这道题被用来讲divide and conquer方法
solution：from beginning to i, find the contiguous subarray ending with i which has the largest sum
public class Solution { public int maxSubArray(int[] A) { int max = A[0]; int[] sum = new int[A.length]; sum[0] = A[0]; for (int i = 1; i < A.length; i++) { sum[i] = Math.max(A[i], sum[i - 1] + A[i]); max = Math.max(max, sum[i]); } return max; }}
这个解法的复杂度是O(n)
More practice: divide and conquer
leetcode 24th round
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。