Coding Patterns
Kadane's Algorithm
Code Templates

Code Templates

Master Kadane’s algorithm patterns with these optimized code templates. Each template includes implementations in JavaScript, Python, Java, C++, Go, and Ruby with detailed explanations.

Refer back to the Concept Guide for theory and understanding.

Standard Kadane (Maximum Subarray Sum)

Problem: Find maximum contiguous subarray sum in linear time. This is the classic LeetCode 53 problem.

function maxSubarray(nums) {
    if (nums.length === 0) return 0;

    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_subarray(nums):
    if not nums:
        return 0

    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) {
        if (nums.length == 0) return 0;

        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;
    }
}
int maxSubarray(vector<int>& nums) {
    if (nums.empty()) return 0;

    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);
    }

    return global_max;
}
func maxSubarray(nums []int) int {
    if len(nums) == 0 {
        return 0
    }

    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_subarray(nums)
    return 0 if nums.empty?

    local_max = nums[0]
    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

Code Breakdown

Key Variables:

  • localMax: Maximum sum of a subarray ending at current position
  • globalMax: Maximum sum found anywhere in the array so far

Algorithm Flow:

  graph LR
    Start[Initialize] --> Step1[Set localMax = first]
    Start --> Step2[Set globalMax = first]
    Step1 --> Step3[Loop through rest]
    Step2 --> Step3
    Step3 --> Step4{Choose extend or restart}
    Step4 --> Restart[localMax = current element]
    Step4 --> Extend[localMax = localMax + current]
    Restart --> Step5[Update globalMax]
    Extend --> Step5
    Step5 --> Done[Return globalMax]

Critical Sections:

  1. Initialization: Both local and global start at first element to handle all-negative arrays
  2. Extension Decision: max(nums[i], localMax + nums[i]) - choose between starting new or extending
  3. Global Update: max(globalMax, localMax) - track best seen so far
Tip: The beauty of Kadane is that we only need two variables. At each position, we decide locally what to do, and carry forward the best result globally.

Kadane with Indices (Track Subarray Position)

Problem: Return both maximum sum and subarray start/end indices. Useful when you need to identify the actual subarray.

function maxSubarrayWithIndices(nums) {
    if (nums.length === 0) return {sum: 0, start: -1, end: -1};

    let localMax = nums[0];
    let globalMax = nums[0];
    let start = 0, end = 0, tempStart = 0;

    for (let i = 1; i < nums.length; i++) {
        if (localMax + nums[i] < nums[i]) {
            localMax = nums[i];
            tempStart = i;  // Start new subarray
        } else {
            localMax += nums[i];
        }

        if (localMax > globalMax) {
            globalMax = localMax;
            start = tempStart;
            end = i;
        }
    }

    return {sum: globalMax, start, end};
}
def max_subarray_with_indices(nums):
    if not nums:
        return {'sum': 0, 'start': -1, 'end': -1}

    local_max = global_max = nums[0]
    start = end = temp_start = 0

    for i in range(1, len(nums)):
        if local_max + nums[i] < nums[i]:
            local_max = nums[i]
            temp_start = i
        else:
            local_max += nums[i]

        if local_max > global_max:
            global_max = local_max
            start = temp_start
            end = i

    return {'sum': global_max, 'start': start, 'end': end}
public class Solution {
    public static class Result {
        int sum, start, end;
        Result(int sum, int start, int end) {
            this.sum = sum; this.start = start; this.end = end;
        }
    }

    public Result maxSubarrayWithIndices(int[] nums) {
        if (nums.length == 0) return new Result(0, -1, -1);

        int localMax = nums[0];
        int globalMax = nums[0];
        int start = 0, end = 0, tempStart = 0;

        for (int i = 1; i < nums.length; i++) {
            if (localMax + nums[i] < nums[i]) {
                localMax = nums[i];
                tempStart = i;
            } else {
                localMax += nums[i];
            }

            if (localMax > globalMax) {
                globalMax = localMax;
                start = tempStart;
                end = i;
            }
        }

        return new Result(globalMax, start, end);
    }
}
struct Result {
    int sum, start, end;
};

Result maxSubarrayWithIndices(vector<int>& nums) {
    if (nums.empty()) return {0, -1, -1};

    int local_max = nums[0];
    int global_max = nums[0];
    int start = 0, end = 0, temp_start = 0;

    for (size_t i = 1; i < nums.size(); ++i) {
        if (local_max + nums[i] < nums[i]) {
            local_max = nums[i];
            temp_start = i;
        } else {
            local_max += nums[i];
        }

        if (local_max > global_max) {
            global_max = local_max;
            start = temp_start;
            end = i;
        }
    }

    return {global_max, start, end};
}
type Result struct {
    Sum   int
    Start int
    End   int
}

func maxSubarrayWithIndices(nums []int) Result {
    if len(nums) == 0 {
        return Result{0, -1, -1}
    }

    localMax := nums[0]
    globalMax := nums[0]
    start := 0
    end := 0
    tempStart := 0

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

        if localMax > globalMax {
            globalMax = localMax
            start = tempStart
            end = i
        }
    }

    return Result{globalMax, start, end}
}
def max_subarray_with_indices(nums)
    return {sum: 0, start: -1, end: -1} if nums.empty?

    local_max = global_max = nums[0]
    start = end = temp_start = 0

    (1...nums.length).each do |i|
        if local_max + nums[i] < nums[i]
            local_max = nums[i]
            temp_start = i
        else
            local_max += nums[i]
        end

        if local_max > global_max
            global_max = local_max
            start = temp_start
            end = i
        end
    end

    {sum: global_max, start: start, end: end}
end

Maximum Product Subarray

Problem: Find maximum contiguous product subarray (LeetCode 152). This variant requires tracking both maximum and minimum because negatives can flip values.

function maxProduct(nums) {
    if (nums.length === 0) return 0;

    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):
    if not nums:
        return 0

    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) {
        if (nums.length == 0) return 0;

        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;
    }
}
int maxProduct(vector<int>& nums) {
    if (nums.empty()) return 0;

    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 {
    if len(nums) == 0 {
        return 0
    }

    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)
    return 0 if nums.empty?

    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

Circular Kadane (Maximum Sum in Circular Array)

Problem: Maximum subarray sum in circular array (LeetCode 918). The maximum can either be within the array (standard Kadane) or wrap around from end to beginning.

function maxSubarraySumCircular(nums) {
    if (nums.length === 0) return 0;

    // Case 1: 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);
    }

    // Case 2: Circular (total - min subarray sum)
    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);
    }

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

    return Math.max(globalMax, total - globalMin);
}
def max_subarray_sum_circular(nums):
    if not nums:
        return 0

    # Case 1: 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)

    # Case 2: 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) {
        if (nums.length == 0) return 0;

        // Case 1: 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);
        }

        // Case 2: Circular (total - min subarray)
        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);
    }
}
int maxSubarraySumCircular(vector<int>& nums) {
    if (nums.empty()) return 0;

    // Case 1: 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);
    }

    // Case 2: 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 {
    if len(nums) == 0 {
        return 0
    }

    // Case 1: 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
        }
    }

    // Case 2: 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)
    return 0 if nums.empty?

    # Case 1: 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

    # Case 2: 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

Practice

Ready to apply these templates? Head over to our Practice Problems page to solve curated LeetCode problems using Kadane’s algorithm.

Pro Tip: Practice writing these templates from memory. The goal is to recognize Kadane problems instantly and implement the right variation without hesitation during interviews.