Maximum circular subarray sum | GeeksforGeeks
Given n numbers (both +ve and -ve), arranged in a circle, fnd the maximum sum of consecutive number.
public static int maxSubarraySumInCircular(List<Integer> A) {
return Math.max(findMaxSubarray(A), findCircularMaxSubarray(A));
}
// Calculates the non-circular solution.
private static int findMaxSubarray(List<Integer> A) {
int maximumTill = 0, maximum = 0;
for (Integer a : A) {
maximumTill = Math.max(a, a + maximumTill);
maximum = Math.max(maximum, maximumTill);
}
return maximum;
}
// Calculates the solution which is circular.
private static int findCircularMaxSubarray(List<Integer> A) {
// Maximum subarray sum starts at index 0 and ends at or before index i.
ArrayList<Integer> maximumBegin = new ArrayList<>();
int sum = A.get(0);
maximumBegin.add(sum);
for (int i = 1; i < A.size(); ++i) {
sum += A.get(i);
maximumBegin
.add(Math.max(maximumBegin.get(maximumBegin.size() - 1), sum));
}
// Maximum subarray sum starts at index i + 1 and ends at the last element.
Integer[] maximumEnd = new Integer[A.size()];
maximumEnd[maximumEnd.length - 1] = 0;
sum = 0;
for (int i = A.size() - 2; i >= 0; --i) {
sum += A.get(i + 1);
maximumEnd[i] = Math.max(maximumEnd[i + 1], sum);
}
// Calculates the maximum subarray which is circular.
int circularMax = 0;
for (int i = 0; i < A.size(); ++i) {
circularMax = Math.max(circularMax, maximumBegin.get(i) + maximumEnd[i]);
}
return circularMax;
}
MaximumSubarrayInCircularArrayConstantSpace.java
private interface IntegerComparator {
Integer compare(Integer o1, Integer o2);
}
private static class MaxComparator implements IntegerComparator {
public Integer compare(Integer o1, Integer o2) {
return o1 > o2 ? o1 : o2;
}
}
private static class MinComparator implements IntegerComparator {
public Integer compare(Integer o1, Integer o2) {
return o1 > o2 ? o2 : o1;
}
}
public static int maxSubarraySumInCircular(List<Integer> A) {
// Finds the max in non-circular case and circular case.
int accumulate = 0;
for (int a : A) {
accumulate += a;
}
return Math.max(findOptimumSubarrayUsingComp(A, new MaxComparator()),
accumulate - findOptimumSubarrayUsingComp(A, new MinComparator()));
}
private static int findOptimumSubarrayUsingComp(List<Integer> A,
IntegerComparator comp) {
int till = 0, overall = 0;
for (int a : A) {
till = comp.compare(a, a + till);
overall = comp.compare(overall, till);
}
return overall;
}
X. One Pass
http://www.cnblogs.com/easonliu/p/3898975.html
Read full article from Maximum circular subarray sum | GeeksforGeeks
Given n numbers (both +ve and -ve), arranged in a circle, fnd the maximum sum of consecutive number.
Case 1: The elements that contribute to the maximum sum are arranged such that no wrapping is there. Kadane’s algorithm will produce the result.
Case 2: The elements which contribute to the maximum sum are arranged such that wrapping is there.
In this case, we change wrapping to non-wrapping. Let us see how. Wrapping of contributing elements implies non wrapping of non contributing elements, so find out the sum of non contributing elements and subtract this sum from the total sum. To find out the sum of non contributing, invert sign of each element and then run Kadane’s algorithm.
Our array is like a ring and we have to eliminate the maximum continuous negative that implies maximum continuous positive in the inverted arrays.
Our array is like a ring and we have to eliminate the maximum continuous negative that implies maximum continuous positive in the inverted arrays.
Finally we compare the sum obtained by both cases, and return the maximum of the two sums.
int maxCircularSum (int a[], int n){ // Case 1: get the maximum sum using standard kadane's algorithm int max_kadane = kadane(a, n); // Case 2: Now find the maximum sum that includes corner elements. int max_wrap = 0, i; for(i=0; i<n; i++) { max_wrap += a[i]; // Calculate array-sum a[i] = -a[i]; // invert the array (change sign) } // max sum with corner elements will be: // array-sum - (-max subarray sum of inverted array) max_wrap = max_wrap + kadane(a, n); // The maximum circular sum will be maximum of two sums return (max_wrap > max_kadane)? max_wrap: max_kadane;}// Standard Kadane's algorithm to find maximum subarray sum// See http://www.geeksforgeeks.org/archives/576 for detailsint kadane (int a[], int n){ int max_so_far = 0, max_ending_here = 0; int i; for(i = 0; i < n; i++) { max_ending_here = max_ending_here + a[i]; if(max_ending_here < 0) max_ending_here = 0; if(max_so_far < max_ending_here) max_so_far = max_ending_here; } return max_so_far;}
-- Same technique can be use to get min subarray sum.
First pass: find max subarray sum.
Second pass: find min subarray sum, and subtract it from total sum.
public int maxConsSum2(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
int soFar = 0;
int max = 0;
int totalSum = 0;
for (Integer i: arr) {
totalSum += i;
// totalSum is used in next step
soFar += i;
soFar = Math.max(soFar, 0);
max = Math.max(max, soFar);
}
int min = 0;
// calculate the min subarray
for (Integer i: arr) {
soFar += i;
soFar = Math.min(soFar, 0);
min = Math.min(min, soFar);
}
return Math.max(max, totalSum - min);
}X. EPI Java Solution: Compute the maximum subarray sum in a circular array
MaximumSubarrayInCircularArray.java ???public static int maxSubarraySumInCircular(List<Integer> A) {
return Math.max(findMaxSubarray(A), findCircularMaxSubarray(A));
}
// Calculates the non-circular solution.
private static int findMaxSubarray(List<Integer> A) {
int maximumTill = 0, maximum = 0;
for (Integer a : A) {
maximumTill = Math.max(a, a + maximumTill);
maximum = Math.max(maximum, maximumTill);
}
return maximum;
}
// Calculates the solution which is circular.
private static int findCircularMaxSubarray(List<Integer> A) {
// Maximum subarray sum starts at index 0 and ends at or before index i.
ArrayList<Integer> maximumBegin = new ArrayList<>();
int sum = A.get(0);
maximumBegin.add(sum);
for (int i = 1; i < A.size(); ++i) {
sum += A.get(i);
maximumBegin
.add(Math.max(maximumBegin.get(maximumBegin.size() - 1), sum));
}
// Maximum subarray sum starts at index i + 1 and ends at the last element.
Integer[] maximumEnd = new Integer[A.size()];
maximumEnd[maximumEnd.length - 1] = 0;
sum = 0;
for (int i = A.size() - 2; i >= 0; --i) {
sum += A.get(i + 1);
maximumEnd[i] = Math.max(maximumEnd[i + 1], sum);
}
// Calculates the maximum subarray which is circular.
int circularMax = 0;
for (int i = 0; i < A.size(); ++i) {
circularMax = Math.max(circularMax, maximumBegin.get(i) + maximumEnd[i]);
}
return circularMax;
}
MaximumSubarrayInCircularArrayConstantSpace.java
private interface IntegerComparator {
Integer compare(Integer o1, Integer o2);
}
private static class MaxComparator implements IntegerComparator {
public Integer compare(Integer o1, Integer o2) {
return o1 > o2 ? o1 : o2;
}
}
private static class MinComparator implements IntegerComparator {
public Integer compare(Integer o1, Integer o2) {
return o1 > o2 ? o2 : o1;
}
}
public static int maxSubarraySumInCircular(List<Integer> A) {
// Finds the max in non-circular case and circular case.
int accumulate = 0;
for (int a : A) {
accumulate += a;
}
return Math.max(findOptimumSubarrayUsingComp(A, new MaxComparator()),
accumulate - findOptimumSubarrayUsingComp(A, new MinComparator()));
}
private static int findOptimumSubarrayUsingComp(List<Integer> A,
IntegerComparator comp) {
int till = 0, overall = 0;
for (int a : A) {
till = comp.compare(a, a + till);
overall = comp.compare(overall, till);
}
return overall;
}
X. One Pass
http://www.cnblogs.com/easonliu/p/3898975.html
Maxsum={ 原问题的最大子数组和；数组所有元素总值-最小子数组和 }
8 void getRes() { 9 int max = 0, min = 0, max_tmp = 0, min_tmp = 0, sum = 0; 10 for (int i = 0; i < n; ++i) { 11 sum += a[i]; 12 max_tmp += a[i]; 13 min_tmp += a[i]; 14 if (max_tmp < 0) max_tmp = 0; 15 if (min_tmp > 0) min_tmp = 0; 16 max = max > max_tmp ? max : max_tmp; 17 min = min < min_tmp ? min : min_tmp; 18 } 19 20 int res = max > (sum - min) ? max : (sum - min); 21 cout << res << endl; 22 }http://www.acmerblog.com/max-sum-rectangle-in-a-matrix-5955.html ??
01 | static int MaxSumLinked(int arr[], int n){ |
02 | int currentSum = arr[0]; |
03 | int ans = currentSum; |
04 | boolean hasNegative = false;//有可能全部都是非负，这时就没必要往后计算 |
05 | for(int i=1; i<n*2-1; i++){ |
06 | if(i < n && arr[i] < 0) hasNegative = true; |
07 | currentSum = Math.max(currentSum+arr[i%n], arr[i%n]); |
08 | ans = Math.max(ans, currentSum); |
09 | if(i == n-1 && !hasNegative) return ans; |
10 | } |
11 | return ans; |
12 | } |
