Largest Sum Contiguous Subarray And “Kadane’s Algorithm”

If you are looking for a solution to leetcode’s Maximum Subarray or an explanation for the Largest Sum Contiguous Subarray aka “Kadane’s Algorithm” then you are in right place.

Problem Statment: find the sum of the largest Subarray in the given array.

Approach 1: Brute Force using 2 loops
Add the integers one at a time, beginning with the index i then note the highest total of all the following components.
The time complexity will become O(n2) if this is repeated (n-i) times for each of the i elements.

nums=[5,4,-1,7,8]
max_sum = 0
for i in range(len(nums)):
    current_sum = 0
    for j in range(i,len(nums)):
       current_sum +=nums[j]
       if current_sum>max_sum:
           max_sum = current_sum
print(max_sum)

Approach 2: using Dynamic Programming
A recursive relation for the maximum subarray problem can be defined as follows:
Let A be an array of n elements, and let maxSubArray(A, i) be the maximum subarray that ends at index i in array A.
Then, the recursive relation can be defined as:

maxSubArray(A, i) = max(maxSubArray(A, i - 1) + A[i], A[i])

This recursive relation states that the maximum subarray ending at index i is either the maximum subarray ending at index i - 1 extended by element A[i], or just the element A[i] itself.

To find the maximum subarray of the entire array, you can use the following recursive function:

def maxSubArray(A, i):
  if i == 0:
    return A[0]
  else:
    return max(maxSubArray(A, i - 1) + A[i], A[i])

# To find the maximum subarray of the entire array A:
max_subarray = max(maxSubArray(A, i) for i in range(len(A)))

This function will find the maximum subarray ending at each index i, and return the maximum of all these subarrays.
The time complexity of the recursive solution for the maximum subarray problem is O(n), where n is the length of the array. This is because the function is called once for each element in the array, and the time taken to compute the maximum subarray for each element is O(1). However, the recursive solution has a space complexity of O(n), because it requires additional space to store the recursive function calls on the call stack.

Approach 3: Iterative + Memo
In this solution dp[i] stores the maximum among the sum of all the sub-arrays ending at index i. And then we can return the maximum of this array dp as the answer.
We have maintained the value of the maximum sum in the variable so we do not need to find the maximum element in dp array separately.

nums= [5,4,-1,7,8]

dp = [0]*len(nums)
big = nums[0]
dp[0] = nums[0]
for i in range(1,len(nums)):
    dp[i] = max(dp[i-1]+nums[i],nums[i])
    if dp[i]>big:
        big = dp[i]
print(big)

The time complexity of the iterative solution for the maximum subarray problem is O(n) and the space complexity is O(n) as we are using dp list.

Approach 4: Kadane’s Algorithm

The Kadane’s algorithm is a dynamic programming approach to finding the maximum sum subarray in an array. The basic idea behind the algorithm is to scan the array from left to right, keeping track of the maximum sum subarray seen so far. At each element, the algorithm updates the maximum sum subarray by comparing the current element to the previous maximum sum subarray. If the current element is larger than the previous maximum sum subarray, the maximum sum subarray is updated to include the current element. If the current element is smaller than the previous maximum sum subarray, the maximum sum subarray is not updated and remains the same. This process is repeated for all elements in the array, and the maximum sum subarray is returned at the end.

Here is the Python code for Kadane’s algorithm:

def max_subarray_sum(arr):
    max_sum = float('-inf')
    current_sum = 0
 
    for i in range(len(arr)):
        current_sum += arr[i]
        max_sum = max(max_sum, current_sum)
 
        if current_sum < 0:
            current_sum = 0
 
    return max_sum
 
 
# test the function
arr = [2, 3, 4, 5, 7]
print(max_subarray_sum(arr))

Scans the array from left to right, keeping track of the maximum sum subarray seen so far. It maintains a variable current_sum that represents the sum of the subarray that ends at the current element and updates the max_sum variable with the maximum of max_sum and current_sum. If current_sum becomes negative, it is reset to 0, since a subarray with a negative sum will always be less than a subarray with no elements.

The time complexity of Kadane’s algorithm is O(n). This means that the algorithm will take approximately linear time to run and The space complexity of Kadane’s algorithm is O(1) since it only uses a few variables to store the intermediate results and does not create any additional data structures.