This problem has optimal sub-problems. Thus it is suitable for dynamic programming.

Assuming array sum_max stores the max of continuous subarray sum of the total array up to i but not include i. Once nums[j] is included, it may or may not change the sum. The initial (wrong) intuitive was to use

sum_max[i] = max(sum_max[i], sum_max[i-1] + nums[i])

However, this produces the largest achievable sum of this array, which does not meet the 'continuous' requirement. To meet the continuous requirement, it is important to 'restart' the subarray from i if including nums[i] changes the max sum that sum_max[i-1] is representing. Thus, the correct iteration is:

sum_max[i] = max(nums[i], sum_max[i-1] + nums[i])

That is to say,, if including nums[i] changes the optimal, reset the optimal with the value of nums[i]. However, this could reduce sum_max[i] overtime if sum_max[i-1] and nums[i] are both negative number. To avoid the optimal sum to be discarded, add the following line to keep the optimal sum that has been discovered so far.

result = max(sum_max[i], result)

Also note that sum_max[i] array is not needed despite it helps the thinking process.

class Solution(object):

def maxSubArray(self, nums):

L = len(nums)

sum_max = nums[0]

result = sum_max

for i in range(1, L):

sum_max = max(nums[i], sum_max + nums[i])

result = max(sum_max, result)

return result