# A DP solution that also finds what the subarray is

• 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])
``````

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