알고리즘/알고리즘 문제 복기
LeetCode - 53. Maximum SubArray
내일도무사히
2021. 2. 13. 20:50
leetcode.com/problems/maximum-subarray/
Answer
배열의 -를 어찌 처리할지 감이 안와서 결국에는 답지를 보게 되었다.
답지에서는 sum의 값이 -일 경우에만 sequence를 리셋하고 계속해서 더하는 방식을 취하고있다.
혹은 다음과 같은 방식으로도 가능하다.
Answer2, Dynamic Programming
state dp[x]를 '이제까지 sub-array에서 해당 값을 포함한 가장 큰 값'이라고 정의했다.
그럴 경우 2가지 경우가 생기게 되는데
1. 해당 배열 현재 인덱스의 '값'이 가장 큰 값일 경우
2. 이전 배열을 연장한 값이 가장 큰 값일 경우 두가지로 나뉘어서
위의코드 11번 라인에서 두가지의 값을 구하고 max를 취해주는 것을 볼 수 있다.