1043. Partition Array for Maximum Sum

1043. Partition Array for Maximum Sum

https://leetcode.com/problems/partition-array-for-maximum-sum/

문제

풀이(최적화 전)

Example 1으로 설명하자면 다음과 같다.

9일 때를 보면
1. ([1,15,7][9]), ([1,15][7,9]), ([1], [15,7,9])로 나누어 질 수 있다.
2. [1,15,7]은 최대값이 45로 알고 있다면 일일이 계산할 필요없이 캐시에서 꺼내오면 될 것이다. 45+9=54이다.
3. [1,15]도 마찬가지로 최대값을 30으로 알고 있다면 30+18=48이다.
4. [1]도 마찬가지로 최대값을 1로 알고 있다면 1+45=46이다.
이 방법으로 구현한 결과는 다음과 같다.

생각보다 많이 느린 것을 알 수 있다.

풀이(최적화 후)

최적화 전 코드는 배열 한 구간에서 최대값을 일일이 찾아야 하지만
최적화 후 코드는 반복문이 실행하는 동안 계속 업데이트 되는 방법으로 바꾸었다.
확실히 시간적인 측면에서 좋아진 것을 알 수 있다.