Kadane's Algorithm Maximum Subarray in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of Kadane's algorithm on this array?

Given the array nums = [-2,1,-3,4,-1,2,1,-5,4], what is the maximum subarray sum found by Kadane's algorithm?

DSA Python

def max_subarray(nums):
    max_current = max_global = nums[0]
    for num in nums[1:]:
        max_current = max(num, max_current + num)
        if max_current > max_global:
            max_global = max_current
    return max_global

nums = [-2,1,-3,4,-1,2,1,-5,4]
print(max_subarray(nums))

A 6

B 7

C 5

D 4

💡 Hint

Think about the contiguous subarray with the largest sum.

Kadane's algorithm finds the maximum sum of a contiguous subarray. For the given array, the subarray [4, -1, 2, 1] sums to 6, which is the maximum.

❓ Predict Output

intermediate

What is the maximum subarray sum for all negative numbers?

Using Kadane's algorithm, what is the maximum subarray sum for nums = [-8, -3, -6, -2, -5, -4]?

DSA Python

def max_subarray(nums):
    max_current = max_global = nums[0]
    for num in nums[1:]:
        max_current = max(num, max_current + num)
        if max_current > max_global:
            max_global = max_current
    return max_global

nums = [-8, -3, -6, -2, -5, -4]
print(max_subarray(nums))

A -5

B -2

C -4

D -3

💡 Hint

Kadane's algorithm returns the largest single element if all are negative.

When all numbers are negative, the maximum subarray is the single largest number, which is -2 here.

🔧 Debug

advanced

What error occurs in this Kadane's algorithm variant?

Consider this code variant of Kadane's algorithm. What error will it raise when run with nums = [-2, -1, -3]?

DSA Python

def max_subarray(nums):
    max_current = max_global = 0
    for num in nums:
        max_current = max(num, max_current + num)
        if max_current > max_global:
            max_global = max_current
    return max_global

nums = [-2, -1, -3]
print(max_subarray(nums))

A Returns 0 incorrectly

B Returns 4 incorrectly

C Returns 3 correctly

D Raises IndexError

💡 Hint

Check initial values and how they affect the result.

Initializing max_current and max_global to 0 causes incorrect result when all numbers are negative. The function returns 0 instead of the correct max sum -1.

🧠 Conceptual

advanced

What does Kadane's algorithm track during iteration?

During Kadane's algorithm execution, what does the variable max_current represent?

A The sum of all elements in the array

B The maximum sum of any subarray found so far

C The maximum sum of a subarray ending at the current position

D The minimum sum of a subarray ending at the current position

💡 Hint

Think about how the algorithm decides to continue or start a new subarray.

max_current holds the maximum sum of a subarray that ends exactly at the current index, helping decide whether to extend or start fresh.

🚀 Application

expert

Find the maximum subarray sum and the subarray itself

Modify Kadane's algorithm to return both the maximum subarray sum and the subarray elements for nums = [3, -2, 5, -1]. What is the correct output?

DSA Python

def max_subarray(nums):
    max_current = max_global = nums[0]
    start = end = s = 0
    for i in range(1, len(nums)):
        if nums[i] > max_current + nums[i]:
            max_current = nums[i]
            s = i
        else:
            max_current += nums[i]
        if max_current > max_global:
            max_global = max_current
            start = s
            end = i
    return max_global, nums[start:end+1]

nums = [3, -2, 5, -1]
print(max_subarray(nums))

A (7, [3, -2, 5, -1])

B (5, [5])

C (8, [3, -2, 5])

D (6, [3, -2, 5])

💡 Hint

Check how the algorithm updates start and end indices.

The maximum sum is 6 from the subarray [3, -2, 5]. The algorithm tracks indices to return the correct subarray.