Geeksforgeeks: Kadane's Algorithm

 

Kadane's Algorithm

Difficulty: Medium

Given an integer array arr[]. You need to find the maximum sum of a subarray.

Examples:

Input: arr[] = [2, 3, -8, 7, -1, 2, 3]
Output: 11
Explanation: The subarray {7, -1, 2, 3} has the largest sum 11.

Input: arr[] = [-2, -4]
Output: -2
Explanation: The subarray {-2} has the largest sum -2.

Input: arr[] = [5, 4, 1, 7, 8]
Output: 25
Explanation: The subarray {5, 4, 1, 7, 8} has the largest sum 25.

Constraints:
1 ≤ arr.size() ≤ 105
-109 ≤ arr[i] ≤ 104

Kadane's Algorithm

Kadane's Algorithm is an efficient solution to the problem of finding the maximum sum of a subarray in an integer array. The algorithm operates in linear time $O(n)$ and requires constant space $O(1)$.

Approach:

1. Initialize two variables:

   • currentSum (the sum of the subarray being considered): It is initialized to the first element of the array.
   • maxSum (the maximum sum encountered so far): It is also initialized to the first element of the array.

2. Iterate through the array:

   • For each element, decide whether to add it to the existing subarray (currentSum) or start a new subarray with the current element. This decision is made by comparing:
     • currentSum + arr[i] (sum including the current element)
     • arr[i] (start a new subarray with the current element)
   • Update currentSum to the maximum of the two.
   • Update maxSum to keep track of the highest sum encountered.

3. Edge Case:

   • If the array contains only negative numbers, Kadane's algorithm will return the largest negative number, which is correct because the subarray with the maximum sum would be just the largest single element.

Code Implementation:

public class Solution {
    public int MaxSubArray(int[] arr) {
        // Initialize variables for current sum and maximum sum.
        int currentSum = arr[0];
        int maxSum = arr[0];
        
        // Iterate through the array from the second element.
        for (int i = 1; i < arr.Length; i++) {
            // Choose to either add the current element to the subarray
            // or start a new subarray from the current element.
            currentSum = Math.Max(arr[i], currentSum + arr[i]);
            
            // Update the maximum sum encountered so far.
            maxSum = Math.Max(maxSum, currentSum);
        }
        
        return maxSum;
    }
}

Explanation:

1. currentSum = Math.Max(arr[i], currentSum + arr[i]):

   • If adding the current element to the currentSum results in a larger sum, continue with the subarray.
   • If not, start a new subarray from the current element.

2. maxSum = Math.Max(maxSum, currentSum):

   • Keep track of the largest sum encountered at each step.

Time Complexity:

• Time Complexity: $O(n)$, where n is the size of the input array. We iterate through the array once, performing constant time operations for each element.
• Space Complexity: $O(1)$, as we are only using a few extra variables for tracking sums, regardless of the input size.

Example Walkthrough:

Example 1:

• Input: arr[] = [2, 3, -8, 7, -1, 2, 3]
• Iteration steps:
  • currentSum = 2, maxSum = 2
  • currentSum = 5, maxSum = 5
  • currentSum = -3, maxSum = 5
  • currentSum = 7, maxSum = 7
  • currentSum = 6, maxSum = 7
  • currentSum = 8, maxSum = 8
  • currentSum = 11, maxSum = 11
• Output: 11

Example 2:

• Input: arr[] = [-2, -4]
• Iteration steps:
  • currentSum = -2, maxSum = -2
  • currentSum = -4, maxSum = -2
• Output: -2

Example 3:

• Input: arr[] = [5, 4, 1, 7, 8]
• Iteration steps:
  • currentSum = 5, maxSum = 5
  • currentSum = 9, maxSum = 9
  • currentSum = 10, maxSum = 10
  • currentSum = 17, maxSum = 17
  • currentSum = 25, maxSum = 25
• Output: 25

Edge Case:

Example 4:

• Input: arr[] = [-1, -2, -3, -4]
• Iteration steps:
  • currentSum = -1, maxSum = -1
  • currentSum = -2, maxSum = -1
  • currentSum = -3, maxSum = -1
  • currentSum = -4, maxSum = -1
• Output: -1 (since all elements are negative, the largest sum is just the least negative element).

Conclusion:

Kadane's Algorithm is a simple yet powerful technique for solving the maximum subarray sum problem in linear time. It is efficient and handles all edge cases, including arrays with all negative numbers.