In this tutorial we will learn about Kadane’s Algorithm with examples in JavaScript.

What is Kadane’s Algorithm?

It is an iterative dynamic programming algorithm. It calculated the maximum sum subarray ending at a particular position by using the maximum sum subarray ending at the previous position.

In this tutorial we learn using JavaScript.

Kadane Algorithm Example

Below is the example of Kadane’s Algorithm using JavaScript. This is efficient method.

Time Complexity : O(N)

Auxiliary Space: O(1)

const arr = [5, -4, -2, 6, -1]
let current_sum =0;
let max_sum = 0;
for(let i=0; i<arr.length; i++){
    current_sum = current_sum + arr[i];
    if(current_sum > max_sum){
        max_sum = current_sum;
    }
    if(current_sum < 0){
        current_sum = 0;
    }
}

console.log(max_sum)
result : 6

For any issue and comment in the comment section below. You can also visit Here.

Thank you for visiting tutorial in FlutterTPoint.