LeetCode - 53. Maximum SubArray

leetcode.com/problems/maximum-subarray/

 

Answer

 

배열의 -를 어찌 처리할지 감이 안와서 결국에는 답지를 보게 되었다.

답지에서는 sum의 값이 -일 경우에만 sequence를 리셋하고 계속해서 더하는 방식을 취하고있다. 

 

혹은 다음과 같은 방식으로도 가능하다.

 

 

 

 

Answer2, Dynamic Programming

 

state dp[x]를 '이제까지 sub-array에서 해당 값을 포함한 가장 큰 값'이라고 정의했다.

 

그럴 경우 2가지 경우가 생기게 되는데 

1. 해당 배열 현재 인덱스의 '값'이 가장 큰 값일 경우

2. 이전 배열을 연장한 값이 가장 큰 값일 경우 두가지로 나뉘어서

 

위의코드 11번 라인에서 두가지의 값을 구하고 max를 취해주는 것을 볼 수 있다.