Question

link

Given n numbers (both +ve and -ve), arranged in a circle, fnd the maximum sum of consecutive number

Solution

First pass: find max subarray sum.

Second pass: find min subarray sum, and subtract it from total sum.

Suggested on G4G

Code

written by me

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);
}