A DP solution that also finds what the subarray is


  • 0

    I am trying to find not only what the max sum is, but also what the subarray is that gives this sum. I used a few variables to remember the start and end point of the max_ending_here. Whenever max_sofar is less than max_ending_here, I update the start and end index of the max subarray:

    class Solution(object):
        def maxSubArray(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            
            max_sofar = float('-inf')
            max_ending_here = float('-inf')
            max_start = 0
            max_end = 0
            current_start = 0
            current_end = 0
            
            for i in range(len(nums)):
                if nums[i] > max_ending_here + nums[i]:
                    current_start = i
                    current_end = i
                    max_ending_here = nums[i]
                else:
                    current_end = i
                    max_ending_here += nums[i]
                
                if max_sofar < max_ending_here:
                    max_start = current_start
                    max_end = current_end
                    max_sofar = max_ending_here
            
            # can also just return max_sofar
            return sum(nums[max_start:max_end+1])
    

Log in to reply
 

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