# Maximum Sum using Kadane's

The Maximum Sum Subarray is a very commonly used example to demonstrate how dynamic programming works. Given an array of numbers, the challenge is to find out

- The maximum subarray sum within the array
- The contiguous subarray that gives you this sum

## Kadane's Algorithm

Okay so moving on to the first problem, a really cool way to find out the maximum subarray sum was proposed by this dude called Kadane^{[1]}. The straightforward version of it is that if you know the maximum sum at a point **A** in your array then the maximum sum at **A+1** is going to be **Maximum at A + Element at A+1** or **Element at A+1** depending on which one is greater.

In practice this is a whole lot simpler that what the above might suggest,

```
const array = [1, -2, 2, 5, -3, -4]
let sum = array[0],
maximum = array[0]
for (let i = 1; i < array.length; i++) {
let element = array[i]
sum = max(sum + element, element)
if (sum > maximum) {
maximum = sum
}
}
console.log(`Maximum sum is ${maximum}`)
```

## Finding the Maximum Subarray

To find the subarray that gives the maximum sum, you can use trackers to keep track of the start and end positions^{[2]}.

```
const array = [1, -2, 2, 5, -3, -4]
let sum = array[0],
maximum = array[0]
let currentStart = 0,
start = 0,
end = 0
for (let i = 1; i < array.length; i++) {
let element = array[i]
sum = max(sum + element, element)
if (sum + element < element) {
currentStart = i + 1
}
if (sum > maximum) {
maximum = sum
start = currentStart
end = i
}
}
console.log(`Maximum sum is ${maximum}`)
console.log(`Maximum subarray is ${start} - ${end}`)
```

## References

[1] - Kadane's algoritm - Wikipedia [2] - Maximum Sum Subarray - Geeksforgeeks