Kadane

• Alternative for sliding window
• How is kadane different from sliding window
• Does this only work for arrays that contain atleast 1 -ve number?
• If an array contains only non-negative values, then yes, the maximum subarray sum will always be equal to the sum of the entire array. This is because there are no negative values that would decrease the overall sum.

Hint: Have two global vars, max sum (negative infinity) and current sum (0). Now iterate through the numbers and keep adding number to current_sum if the current sum is greater than max sum, if current sum goes less than 0 assign 0 to current sum. Result = Max sum

edge_case If the max sum is not initialised with negative integer than all negative array will give wrong answer.

Initialize: max_so_far = INT_MIN max_ending_here = 0

Loop for each element of the array

(a) max_ending_here = max_ending_here + a[i] (b) if(max_so_far < max_ending_here) max_so_far = max_ending_here (c) if(max_ending_here < 0) max_ending_here = 0 return max_so_far

Intuition

• initialization_phase

Code

Python minimum integer

import sys
min_int = -sys.maxsize - 1
print(min_int)  # Output: -9223372036854775808

def kadane(nums):
    max_sum = float('-inf')
    current_sum = 0
 
    for num in nums:
        current_sum += num
        if current_sum > max_sum:
            max_sum = current_sum
        if current_sum < 0:
            current_sum = 0
 
    return max_sum

Problems

• Maximum of all subarrays of size k