Kandane's Algorithm O(n)


  • 0
    T

    I find this by far the easiest solution as it's intuitive and is very close logically to the Brute Force method.

    Kandane's works by having two variables indicating the current_max, and global_max each initialized to the 0th position of the starting array. As we iterate from 1..i..(n - 1) elements we indicate the maximum sub-array for the previous i positions with current_max. There can be only two possibilities either the maximum sub-array at position i is A[i] i.e. the maximum sub-array is that and only that position in the array. Or, there is some M (max) elements before A[i], plus the newly discovered A[i], this contains the maximal sub-array so far. If the A[i]th element is greater than our current maximum then we know it's part of maximal subarray, otherwise our global sum contains the max subarray so far.

    An example:

    [-2, 3, 2, -1]

    i : 0 ->
    (Curr Max and Global Max are initialized)
    curr_max = A[0] = -2
    global_max = A[0] = -2

    i : 1 ->
    (
    curr_max = max(A[i], curr_max + A[i]) = max(3, (-2 + 3)) = 3
    3 > -2 so update global_max
    global_max = 3

    i : 2 ->
    curr_max = max(A[i], curr_max + A[i]) = max(2, (3 + 2)) = 5
    5 > 3 so update global_max
    global_max = 5

    i : 3 ->
    curr_max = max(A[i], curr_max + A[i]) = max(-1, ((5 + -1)) = 4
    4 < 5
    Continue

    We reach the end of the array so return our global_max which is 5 tadah!

    Code:

    int maxSubArray(vector<int>& nums)
    {
    int global_max = nums[0], curr_max = nums[0];
    for(int i = 1; i < nums.size(); ++i)
    {
    curr_max = max(nums[i], curr_max + nums[i]);
    if(curr_max > global_max)
    global_max = curr_max;
    }
    return global_max;
    }


  • 0
    D

    Note that a requirement for Kandane's algorithm is at least one positive number. To deal with that, it can be augmented by doing a first sweep to check if all of the numbers in the list aren't negative. If they are, then return the largest and skip the Kandane process.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.