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

  • 0
        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.