C# Solution using stateful DP; O(N) complexity; O(1) Space


  • 0
    D

    The solution is a little tricky and subtle and needs to be discussed.

    Let's start off with the Naive O(N^2) solution:


    public class Solution
    {
        public int MaxSubArray(int[] nums)
        {
            int maxSum = 0;//nothing to sum, yet
            int length = nums.Length;
            
            if (length > 0)
            {
                maxSum = nums[i];//set first element to max
    
                for(int i = 0; i < length; i++)
                {
                    int sum = nums[i];
    
                    if(sum > maxSum)//Check if each starting element > max
                    {
                        maxSum = sum;
                    }
    
                    for (int j = i + 1; j < length; j++)
                    {
                        sum += nums[j];
    
                        if(sum > maxSum)//check when the *running* sum exceeds max
                        {
                            maxSum = sum;
                        }
                    }
                }
            }
    
            return maxSum;
        }
    }
    

    The code does work; albeit, inefficiently. Each i starts a new sum. Each j is a running tally of the sum from that i. For each i and each j, when maxSum has been exceeded, it is set to the current sum. Not much thought is needed to write that code, but the trade-off is efficiency. It is probably the easiest solution but does not meet the O(N) requirement.

    So how do we get to an O(N) requirement? Deeper analysis is needed. In the O(N^2) Solution, each i is the starting point of a running sum and each sub-loop continues until n. There's a lot of redundant checking and calculation. One idea or approach to eliminate redundant checking and calculation is to try to apply Dynamic Programming principles to the problem.

    In this problem, the recurrence relation, itself, is dynamic and has two states: 1) if the running sum is > 0, then sum = sum + Ai, 2) if the running sum is < 1, the sum is reset to Ai. In this way, it is a "stateful" DP problem (an atypical memoization that does not require an array for tracking states of each n)--it is a running state that, itself, is dynamic.

    So, the real "elephant" in the room is that any value < 1 changes the state? To answer that question, let's consider the behavior. If we use the "vector" language, any time the vector direction changes, the co-related state changes. We can consider each contiguous sub-array it's own vector. Whenever the running sum changes direction, that implies that we are starting a new vector and/or terminating the current vector.

    There are 3 states for the running sum vector:

    • Moving in a positive direction
    • Moving in a negative direction
    • Not moving

    For calculating the Maximum, we are concerned with the positive direction. We want the value of the vector (sub-array) with the maximum amplitude (sum). Each Ai that is greater than 0, automatically has greater amplitude than any vector, whose direction is not moving and/or negative. The key here is that an element Ai, that behaves this way, gives us a way to make a stateful DP.

    Examples:

    • {2, -1 , 3} = 4; //The direction never changed
    • {1, -2, 3} = 3 //The direction changed at Ai = 3 (or {1, -2} is a negative vector)
    • {-1, 0, 0, 0) = 0 //The direction changed at Ai = 0
    • {-1, -2, -3, -4} = -1 //The direction never changed, but note that element Ai=-1 is the max

    There already solutions done this way, but without adequate explanation in my honest opinion.

    Without further adieu here is the stateful DP code that I used that resulted in O(N) complexity with O(1) space:


    /// <summary>
    /// Find the contiguous subarray within an array (containing at least one 
    /// number) which has the largest sum.
    /// 
    /// For example, given the array[-2, 1, -3, 4, -1, 2, 1, -5, 4],
    /// the contiguous subarray[4, -1, 2, 1] has the largest sum = 6.
    /// </summary>
    public class Solution
    {
        public int MaxSubArray(int[] nums)
        {
            int maxSum = 0;
            int length = nums.Length;
            
            if (length > 0)
            {
                int sum = maxSum = nums[0];
    
                for(int i = 1; i < length; i++)
                {
                    if(sum > 0)
                    {
                        sum += nums[i];
                    }
                    else
                    {
                        sum = nums[i];
                    }
    
                    if(sum > maxSum)
                    {
                        maxSum = sum;
                    }
                }
            }
    
            return maxSum;
        }
    }

Log in to reply
 

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