Kadane's Algorithm

Problem Statement: here

PS Understanding:
Given an array, we have to find the substring with the largest sum using Kadane's algorithm.

Solution:

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

current_sum = arr[0]
max_sum = arr[0]

for i in range(1, len(arr)):
    current_sum = max(arr[i], current_sum + arr[i])
    max_sum = max(max_sum, current_sum)

print(max_sum)

• Kadane’s algorithm works by scanning the array once and deciding at each element whether it is better to continue the current subarray or start a new one from that element.
• We keep two variables: current_sum, which stores the sum of the subarray we are currently building, and max_sum, which stores the best (maximum) sum found so far.
• Initially, both are set to the first element. Then for every next element, we update current_sum by taking the maximum of two choices: either start fresh from the current element (arr[i]) or add it to the previous sum (current_sum + arr[i]).
• This step ensures that if the previous sum becomes negative, we discard it and restart.
• After updating current_sum, we compare it with max_sum and update max_sum if needed.
• By the end of the loop, max_sum holds the maximum subarray sum.
• This works efficiently in one pass because it never recalculates subarrays and always keeps track of the best possible sum at each step.