21-11-25
unsolved
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.
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
l=len(nums)
if l==1:
return nums[0]
dp=[0]*l#0th:
dp[0]=nums[0]
maxNum=dp[0]
for i in range(1,l):
dp[i]=max(nums[i],nums[i]+dp[i-1])
if maxNum<dp[i]:
maxNum=dp[i]
return maxNum
옛날에 백준에서 풀어놓고 까먹어서 못 풀었다.
찾아보니, 해당 문제를 해결하는 알고리즘이 잘 알려져있었다.
최대합 부분수열 구하는 알고리즘. O(N)
Dynamic Programming - 어떤 문제를 해결 가능한 하위 문제로 나누어 푸는 방법.
dp[i]: i번째 원소를 마지막으로 하는 subarray의 최대합.
이 때 다음과 같은 점화식이 성립한다.
dp[i]=max(nums[i],nums[i]+dp[i-1])
말로 한 번 더 정리해보자.
i번째 원소를 마지막으로 하는 최대합을 가진 subarray를 구하려면,
1) i-1번째 원소를 마지막으로 하는 최대합 subarry에다가 i번째 원소를 더하거나
2) i 번째 원소로만 subarray를 만들거나
두 가지 경우 밖에 없다.
이런 알고리즘은 그냥 기억해야하나 싶다.