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

• ``````    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;
}
``````

}

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