Kadane's Algorithm


#array
- 1 minutes read - 108 words

Description

It scans the given array A [ 1 … n ] from left to right. In the ith step, it computes the subarray with the largest sum ending at i; this sum is maintained in variable max_so_far

Wiki

Code

"""
Given an integer array nums, find the contiguous subarray 
(containing at least one number) which has the largest sum and return its sum.
"""

dp = [1,2,3,4]

# Kadane’s Algorithm:
max_so_far = 0 # -math.inf to include negative numbers
max_ending_here = 0

for i in range(len(dp)): 
    max_ending_here = max_ending_here + dp[i] 
    if (max_so_far < max_ending_here): 
        max_so_far = max_ending_here 

    if max_ending_here < 0: 
        max_ending_here = 0

return max_so_far