ProgramGuru.org

ProgramGuru.org

Maximum Subarray Sum using Kadane's Algorithm - Optimal Approach

Maximum Subarray Sum using Kadane's Algorithm - Optimal Approach

Algorithm Steps

  1. Given an integer array arr.
  2. Initialize two variables: max_sum and current_sum with the value of the first element.
  3. Iterate through the array starting from index 1.
  4. At each step, update current_sum as the maximum of the current element or current_sum + current_element.
  5. Update max_sum if current_sum is greater than max_sum.
  6. After the loop, return max_sum as the result.

Find Maximum Subarray Sum using Kadane's Algorithm Code

Python
JavaScript
Java
C++
C
def max_subarray_sum(arr):
    max_sum = current_sum = arr[0]
    for num in arr[1:]:
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)
    return max_sum

# Sample Input
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print("Maximum Subarray Sum:", max_subarray_sum(arr))