CA 10 - Kadane's Algorithm

Problem Statement

You are given an integer array arr[]. You need to find the maximum sum of a subarray (containing at least one element) in the array.

Note: A subarray is a continuous part of an array.

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.

For this problem, my goal was to properly understand how subarrays work and avoid checking all possible subarrays since that would be inefficient. I wanted to learn a more optimal way to solve maximum sum problems and overall improve my problem-solving efficiency.

For the solution, I used Kadane’s Algorithm since it’s the most efficient approach. The idea is to keep a running sum and if it ever becomes negative, reset it to zero because it won’t help in getting a maximum sum. At the same time, I keep track of the maximum sum seen so far, so in the end I get the best possible subarray sum without unnecessary checks.

Solution Code (Python)

a = [2, 3, -8, 7, -1, 2, 3]

c = 0
m = a[0]

for x in a:
    c += x
    if c > m:
        m = c
    if c < 0:
        c = 0

print(m)