Dynamic Programming with Step by Step Comments - O(n)


  • 0
    C
        public class Solution {
    
        public int MaxSubArray(int[] nums) {
    
        if (nums == null || nums.Length == 0)
        {
            return 0;
        }
        
        if (nums.Length == 1)
        {
            return nums[0];
        }
        
        // at this point we can be sure that we have more than one element.
        int[] dp = new int[nums.Length];
        
        // maximum sub array sum till now.
        var maxTillNow = nums[0];
        
        // setting the initiation max, its the first item.
        dp[0] = nums[0];
        
        for (int i=1; i < nums.Length; i++)
        {
            // dp maintains the sum of the subarray
            // we reset if we find an element when contributed to the subarray decreases it.
            // meaning add until we are going up, if not we set the current item as the start point
            // by doing do we start a new sub array calculation.
            dp[i] = Math.Max(nums[i] + dp[i-1], nums[i]);
            
            // check if we have seen a maximum sub array as large as the one we are in.
            maxTillNow = Math.Max(maxTillNow, dp[i]);
        }
        
        return maxTillNow;
    }
    

    }


Log in to reply
 

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