Kadane Algorithm

Classic Problem: Finding the largest subarray

Explain:

https://www.geeksforgeeks.org/largest-sum-contiguous-subarray

Leetcode

Loading...LeetCode

Loading...LeetCode

=> PATTERN: Remember this code

def max_subarray(A):
    max_current = max_global = nums[0]

    for num in nums[1:]:
        max_current = max(num, max_current + num)
        max_global = max(max_global, max_current)

    return max_global

Enhancement: Now we have maximum subarray. Now Calculate maximum subsequence from this subarray.

For example: The subarray [2, -1, 2, 3, 4] is the subarray with the maximum sum, and [2, 2, 3, 4] is the subsequence with the maximum sum.

=> PATTERN: Remember this code

def max_subarray(A):
    max_current = max_global = max_subsequence = nums[0]

    for num in nums[1:]:
        max_current = max(num, max_current + num)
        max_global = max(max_global, max_current)
        max_subsequence = max(max_subsequence, max_subsequence + num, num)

    return max_global, max_subsequence

ADVANCE: Find that subarray

=> Remember this code

def max_subarray(nums):
    max_sum = nums[0]
    start = end = 0
    current_sum = nums[0]
    current_start = 0

    for i in range(1, len(nums)):
        if nums[i] > current_sum + nums[i]:
            current_sum = nums[i]
            current_start = i
        else:
            current_sum += nums[i]

        if current_sum > max_sum:
            max_sum = current_sum
            start = current_start
            end = i

    return nums[start:end+1]