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.
From http://en.wikipedia.org/wiki/Maximum_subarray_problem
Kadane's algorithm consists of a scan through the array values, computing at each position the maximum (positive sum) subarray ending at that position. This subarray is either empty (in which case its sum is zero) or consists of one more element than the maximum subarray ending at the previous position.
Read full article from LeetCode – Maximum Subarray (Java)
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.
From http://en.wikipedia.org/wiki/Maximum_subarray_problem
Kadane's algorithm consists of a scan through the array values, computing at each position the maximum (positive sum) subarray ending at that position. This subarray is either empty (in which case its sum is zero) or consists of one more element than the maximum subarray ending at the previous position.
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; } } |
Above program can be optimized further, if we compare max_so_far with max_ending_here only if max_ending_here is greater than 0. The implementation handles the case when all numbers in array are negative. From http://www.geeksforgeeks.org/largest-sum-contiguous-subarray/
int maxSubArraySum(int a[], int size){ int max_so_far = a[0], i; int curr_max = a[0]; for (i = 1; i < size; i++) { curr_max = max(a[i], curr_max+a[i]); max_so_far = max(max_so_far, curr_max); } return max_so_far;}
No comments:
Post a Comment