Categories

# 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 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