CA 10 - 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 re