문제

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Example 2:

Input: nums = [1]
Output: 1

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23

Constraints:

• $1 <=$ nums.length $<= 3 * 10^4$
• $10^5 <=$ nums[i] $<= 10^5$

Follow up : If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Python 풀이

def maxSubArray(nums):
    for i in range(1, len(nums)):
        nums[i] = max(nums[i-1] + nums[i], nums[i])
    return max(nums)

접근법

DP를 이용하자!
[-2,1,-3,4,-1,2,1,-5,4] 여기서 처음부터 쭉 더해보다가 어느 시점에서 더해봤자 더 작아지는 부분이 있으면 다시 그 부분부터 시작해서 더해간다.

풀이법

예제 1번 [-2,1,-3,4,-1,2,1,-5,4]을 이용해서 풀어보면

1. nums[i] = max(nums[i-1] + nums[i], nums[i])에서 이 전의 값과 지금의 값의 합, 지금의 값 둘 중에 큰 값으로 대체한다. 인덱스가 1부터 시작이므로 [-2,1,-3,4,-1,2,1,-5,4] 여기서 -2 + 1 = -1, 1 둘 중에 1이 더 크니까 [-2,1,-3,4,-1,2,1,-5,4] 가 된다.

2. 1 + (-3) = -2, -3 둘 중에 -2가 더 크므로 [-2,1,-2,4,-1,2,1,-5,4] 이다.

3. -2 + 4 = 2, 4 둘 중 원래 있던 4가 더 크므로 지금까지 앞에서 더해온 것들을 가지고 계속 더해가는건 더 손해므로 과감히 버리고 새출발을 한다.

4. 이런 식으로 진행해 나가면 가장 큰 부분 합을 구할 수 있다.