Kadane’s Algorithm for maximum sum subarray with Indices [Handles Negatives] O(n)

This algorithm can be used to calculate the maximum sum subarray with indices in any given array (length n) of integers in O(n) Time and O(1) space.

package algos;

class solution {

    public solution() {}

    public int getMaxSum(int[] arr) {
        int max = arr[0], start = 0, end = 0, mstart = 0, mend = 0, currmax = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > arr[i] + currmax) {
                currmax = arr[i];
                start = i;
            } else {
                currmax = currmax + arr[i];
            }
            end = i;
            if (currmax > max) {
                max = currmax;
                mstart = start;
                mend = end;
            }
        }
        System.out.println("start:" + mstart + " end:" + mend);
        return max;
    }
}

public class kadanes {
    public static void main(String[] args) {
        int[] arr = {-1, -4, -2};
        solution sol = new solution();
        System.out.println(sol.getMaxSum(arr));
    }
}

Output

start:0 end:0
 -1

This algorithm can be used to find out the maximum sum rectangular sub-matrix in an mxn matrix in O(n*n*m) time and O(m) space.

Javasript (ES6) Solution

const getMaxSum = (arr) => {
  if (!arr)
    return;
  let currMax = arr[0];
  let max = currMax;
  let currStart = 0;
  let currEnd = arr.length;
  let maxStart = currStart;
  let maxEnd = currEnd;
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > arr[i] + currMax) {
      currStart = i;
      currMax = arr[i];
    } else {
      currMax += arr[i];
    }
    currEnd = i;
    if (currMax > max) {
      max = currMax;
      maxStart = currStart;
      maxEnd = currEnd;
    }
  }
  console.log(`start: ${maxStart}`);
  console.log(`end: ${maxEnd}`);
  console.log(`max: ${max}`);
};

getMaxSum([1, 2, -9, 9, 67, -1]);

// output
/*
"start: 3"
"end: 4"
"max: 76"
*/

Demo