Problems

Master Kadane’s algorithm by solving these carefully selected maximum subarray sum problems. Each problem builds your understanding of dynamic programming concepts and optimization techniques.

Refer to the Code Templates for reference implementations.

Easy Problems

1. Maximum Subarray

Brief: Find the contiguous subarray with the largest sum and return its sum.
Why this pattern?: Classic Kadane’s algorithm problem where we track local and global maximums.
Key Insight: At each position, choose between extending current subarray or starting fresh.

Algorithm Visualization:

  graph TD
    Start[Start with first element] --> Loop{For each element}
    Loop --> Decision{Extend or Restart?}
    Decision -->|Restart| Restart[localMax = current element]
    Decision -->|Extend| Extend[localMax += current element]
    Restart --> Global[Update globalMax]
    Extend --> Global
    Global --> Next{More elements?}
    Next -->|Yes| Loop
    Next -->|No| Return[Return globalMax]

Solution:

function maxSubArray(nums) {
    let localMax = nums[0];
    let globalMax = nums[0];

    for (let i = 1; i < nums.length; i++) {
        localMax = Math.max(nums[i], localMax + nums[i]);
        globalMax = Math.max(globalMax, localMax);
    }

    return globalMax;
}

def max_sub_array(nums):
    local_max = global_max = nums[0]

    for i in range(1, len(nums)):
        local_max = max(nums[i], local_max + nums[i])
        global_max = max(global_max, local_max)

    return global_max

public class Solution {
    public int maxSubArray(int[] nums) {
        int localMax = nums[0];
        int globalMax = nums[0];

        for (int i = 1; i < nums.length; i++) {
            localMax = Math.max(nums[i], localMax + nums[i]);
            globalMax = Math.max(globalMax, localMax);
        }

        return globalMax;
    }
}

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int localMax = nums[0];
        int globalMax = nums[0];

        for (size_t i = 1; i < nums.size(); ++i) {
            localMax = max(nums[i], localMax + nums[i]);
            globalMax = max(globalMax, localMax);
        }

        return globalMax;
    }
};

func maxSubArray(nums []int) int {
    localMax := nums[0]
    globalMax := nums[0]

    for i := 1; i < len(nums); i++ {
        if localMax+nums[i] > nums[i] {
            localMax += nums[i]
        } else {
            localMax = nums[i]
        }
        if localMax > globalMax {
            globalMax = localMax
        }
    }

    return globalMax
}

def max_sub_array(nums)
    local_max = global_max = nums[0]

    (1...nums.length).each do |i|
        local_max = [nums[i], local_max + nums[i]].max
        global_max = [global_max, local_max].max
    end

    global_max
end

Medium Problems

2. Maximum Product Subarray

Brief: Find the contiguous subarray with the largest product.
Why this pattern?: Similar to Kadane, but we must track both maximum and minimum (negatives flip values).
Key Insight: Negative numbers can turn minimum product into maximum, so track both.

Algorithm Visualization:

  graph TD
    Start[Initialize localMax, localMin, globalMax] --> Loop{For each element}
    Loop --> Save[Save tempMax = localMax]
    Save --> Update[Update localMax and localMin]
    Update -->|Three choices| Choice[current element, tempMax*current, localMin*current]
    Choice --> localMax[localMax = max of three]
    Choice --> localMin[localMin = min of three]
    localMin --> Global[Update globalMax]
    localMax --> Global
    Global --> Next{More elements?}
    Next -->|Yes| Loop
    Next -->|No| Return[Return globalMax]

Solution:

function maxProduct(nums) {
    let localMax = nums[0];
    let localMin = nums[0];
    let globalMax = nums[0];

    for (let i = 1; i < nums.length; i++) {
        const tempMax = localMax;

        localMax = Math.max(nums[i], localMax * nums[i], localMin * nums[i]);
        localMin = Math.min(nums[i], tempMax * nums[i], localMin * nums[i]);

        globalMax = Math.max(globalMax, localMax);
    }

    return globalMax;
}

def max_product(nums):
    local_max = local_min = global_max = nums[0]

    for i in range(1, len(nums)):
        temp_max = local_max

        local_max = max(nums[i], local_max * nums[i], local_min * nums[i])
        local_min = min(nums[i], temp_max * nums[i], local_min * nums[i])

        global_max = max(global_max, local_max)

    return global_max

public class Solution {
    public int maxProduct(int[] nums) {
        int localMax = nums[0];
        int localMin = nums[0];
        int globalMax = nums[0];

        for (int i = 1; i < nums.length; i++) {
            int tempMax = localMax;

            localMax = Math.max(nums[i], Math.max(localMax * nums[i], localMin * nums[i]));
            localMin = Math.min(nums[i], Math.min(tempMax * nums[i], localMin * nums[i]));

            globalMax = Math.max(globalMax, localMax);
        }

        return globalMax;
    }
}

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int local_max = nums[0];
        int local_min = nums[0];
        int global_max = nums[0];

        for (size_t i = 1; i < nums.size(); ++i) {
            int temp_max = local_max;

            local_max = max({nums[i], local_max * nums[i], local_min * nums[i]});
            local_min = min({nums[i], temp_max * nums[i], local_min * nums[i]});

            global_max = max(global_max, local_max);
        }

        return global_max;
    }
};

func maxProduct(nums []int) int {
    localMax := nums[0]
    localMin := nums[0]
    globalMax := nums[0]

    for i := 1; i < len(nums); i++ {
        tempMax := localMax

        candidates := []int{nums[i], localMax * nums[i], localMin * nums[i]}
        sort.Ints(candidates)
        localMax = candidates[2]
        localMin = candidates[0]

        if localMax > globalMax {
            globalMax = localMax
        }
    }

    return globalMax
}

def max_product(nums)
    local_max = local_min = global_max = nums[0]

    (1...nums.length).each do |i|
        temp_max = local_max

        local_max = [nums[i], local_max * nums[i], local_min * nums[i]].max
        local_min = [nums[i], temp_max * nums[i], local_min * nums[i]].min

        global_max = [global_max, local_max].max
    end

    global_max
end

3. Maximum Sum Circular Subarray

Brief: Find maximum possible sum of a non-empty subarray in a circular array.
Why this pattern?: Maximum can be within array (standard Kadane) or wrap around (total minus minimum subarray).
Key Insight: Circular maximum equals total sum minus minimum subarray sum.

Algorithm Visualization:

  graph TD
    Start[Start] --> Kadane1[Standard Kadane for max]
    Kadane1 --> Max[Get globalMax]
    Max --> Total[Calculate total sum]
    Total --> Kadane2[Reverse Kadane for min]
    Kadane2 --> Min[Get globalMin]
    Min --> Check{All negative?}
    Check -->|Yes| ReturnMax[Return globalMax]
    Check -->|No| Circular[total - globalMin]
    Circular --> Final[Return max of globalMax and circular]

Solution:

function maxSubarraySumCircular(nums) {
    // Standard Kadane
    let localMax = nums[0];
    let globalMax = nums[0];

    for (let i = 1; i < nums.length; i++) {
        localMax = Math.max(nums[i], localMax + nums[i]);
        globalMax = Math.max(globalMax, localMax);
    }

    // Circular case
    const total = nums.reduce((a, b) => a + b, 0);
    let localMin = nums[0];
    let globalMin = nums[0];

    for (let i = 1; i < nums.length; i++) {
        localMin = Math.min(nums[i], localMin + nums[i]);
        globalMin = Math.min(globalMin, localMin);
    }

    // All negative case
    if (globalMin === total) return globalMax;

    return Math.max(globalMax, total - globalMin);
}

def max_subarray_sum_circular(nums):
    # Standard Kadane
    local_max = global_max = nums[0]

    for i in range(1, len(nums)):
        local_max = max(nums[i], local_max + nums[i])
        global_max = max(global_max, local_max)

    # Circular case
    total = sum(nums)
    local_min = global_min = nums[0]

    for i in range(1, len(nums)):
        local_min = min(nums[i], local_min + nums[i])
        global_min = min(global_min, local_min)

    # All negative case
    if global_min == total:
        return global_max

    return max(global_max, total - global_min)

public class Solution {
    public int maxSubarraySumCircular(int[] nums) {
        // Standard Kadane
        int localMax = nums[0];
        int globalMax = nums[0];

        for (int i = 1; i < nums.length; i++) {
            localMax = Math.max(nums[i], localMax + nums[i]);
            globalMax = Math.max(globalMax, localMax);
        }

        // Circular case
        int total = 0;
        for (int num : nums) total += num;

        int localMin = nums[0];
        int globalMin = nums[0];

        for (int i = 1; i < nums.length; i++) {
            localMin = Math.min(nums[i], localMin + nums[i]);
            globalMin = Math.min(globalMin, localMin);
        }

        // All negative case
        if (globalMin == total) return globalMax;

        return Math.max(globalMax, total - globalMin);
    }
}

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        // Standard Kadane
        int local_max = nums[0];
        int global_max = nums[0];

        for (size_t i = 1; i < nums.size(); ++i) {
            local_max = max(nums[i], local_max + nums[i]);
            global_max = max(global_max, local_max);
        }

        // Circular case
        int total = 0;
        for (int num : nums) total += num;

        int local_min = nums[0];
        int global_min = nums[0];

        for (size_t i = 1; i < nums.size(); ++i) {
            local_min = min(nums[i], local_min + nums[i]);
            global_min = min(global_min, local_min);
        }

        // All negative case
        if (global_min == total) return global_max;

        return max(global_max, total - global_min);
    }
};

func maxSubarraySumCircular(nums []int) int {
    // Standard Kadane
    localMax := nums[0]
    globalMax := nums[0]

    for i := 1; i < len(nums); i++ {
        if localMax+nums[i] > nums[i] {
            localMax += nums[i]
        } else {
            localMax = nums[i]
        }
        if localMax > globalMax {
            globalMax = localMax
        }
    }

    // Circular case
    total := 0
    for _, num := range nums {
        total += num
    }

    localMin := nums[0]
    globalMin := nums[0]

    for i := 1; i < len(nums); i++ {
        if localMin+nums[i] < nums[i] {
            localMin += nums[i]
        } else {
            localMin = nums[i]
        }
        if localMin < globalMin {
            globalMin = localMin
        }
    }

    // All negative case
    if globalMin == total {
        return globalMax
    }

    circularMax := total - globalMin
    if circularMax > globalMax {
        return circularMax
    }
    return globalMax
}

def max_subarray_sum_circular(nums)
    # Standard Kadane
    local_max = global_max = nums[0]

    (1...nums.length).each do |i|
        local_max = [nums[i], local_max + nums[i]].max
        global_max = [global_max, local_max].max
    end

    # Circular case
    total = nums.sum
    local_min = global_min = nums[0]

    (1...nums.length).each do |i|
        local_min = [nums[i], local_min + nums[i]].min
        global_min = [global_min, local_min].min
    end

    # All negative case
    return global_max if global_min == total

    [global_max, total - global_min].max
end

Recommended Study Order

Start with Maximum Subarray to grasp the basics, then move to Maximum Product Subarray to understand variations with negatives. Finally, tackle Maximum Sum Circular Subarray to master the wrap-around technique.

For more pattern theory, visit the Concept Guide.

Pro Tip: Always verify your understanding by tracing through examples. Write out localMax, globalMax values at each step to build intuition.