Kadane's Algorithm (DSA)

Problem statement:(👈click here for GFG)

Given an array Arr[] of N integers. Find the contiguous sub-array(containing at least one number) which has the maximum sum and return its sum.

Example 1:

Input:
N = 5
Arr[] = {1,2,3,-2,5}
Output:
9
Explanation:
Max subarray sum is 9
of elements (1, 2, 3, -2, 5) which 
is a contiguous subarray.

Example 2:

Input:
N = 4
Arr[] = {-1,-2,-3,-4}
Output:
-1
Explanation:
Max subarray sum is -1 
of element (-1)

Your Task:
You don't need to read input or print anything. The task is to complete the function maxSubarraySum() which takes Arr[] and N as input parameters and returns the sum of subarray with maximum sum.

Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)

Constraints:
1 ≤ N ≤ 106
-107 ≤ A[i] ≤ 107

Solution:

One of the efficient approaches to solve this problem in O(N) time complexity and O(1) space complexity is to use Kadane's algorithm.

Algorithm:

• Initialize two variables 'maxSoFar' and 'maxEndingHere' to the first element of the array.

• Traverse the array from index 1 to N-1.

• For each element, calculate the maximum sum of subarray ending at that element by adding the current element to 'maxEndingHere', and update the 'maxEndingHere' to the maximum of either the current element or the sum obtained by adding the current element to 'maxEndingHere'.

• Update the 'maxSoFar' to the maximum of 'maxSoFar' and 'maxEndingHere'.

• Return the value of 'maxSoFar'.

Here's the JavaScript code for the same:

function maxSubarraySum(arr, n) {

  let maxSoFar = arr[0];

  let maxEndingHere = arr[0];

  for (let i = 1; i < n; i++) {

    maxEndingHere = Math.max(arr[i], maxEndingHere + arr[i]);

    maxSoFar = Math.max(maxSoFar, maxEndingHere);

  }

  return maxSoFar;

}

Note: This code assumes that the input array has at least one element.

2nd Approach: The time complexity of this approach is O(N^2), which is not optimal.

Algorithm:

• Initialize a variable named 'maxSum' to -Infinity.

• Traverse the array from index 0 to N-1 as the starting index of the subarray.

• For each starting index, initialize a variable named 'sum' to 0.

• Traverse the array from the starting index to N-1 as the ending index of the subarray.

• For each ending index, add the array element to 'sum' and update 'maxSum' to the maximum of 'maxSum' and 'sum'.

• Return the value of 'maxSum'.

The above algorithm has a time complexity of O(N^2).

Here's the JavaScript code for the same:

function maxSubarraySum(arr, N) {

  let maxSum = -Infinity;

  for (let i = 0; i < N; i++) {

    let sum = 0;

    for (let j = i; j < N; j++) {

      sum += arr[j];

      if (sum > maxSum) {

        maxSum = sum;

      }

    }

  }

  return maxSum;

}

Note: This code assumes that the input array has at least one element.