Python solution with thought process shared


  • 0
    D

    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


  • 0
    D

    found that the indentation was removed, try to post again.
    """
    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
    """


  • 0
    D

    Finally figured out the correct way of posting code.

    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
    

Log in to reply
 

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