[leetcode] 1191. K-Concatenation Maximum Sum

문제 : https://leetcode.com/problems/k-concatenation-maximum-sum/

---

A : arr 배열 내 앞에서부터 최대부분합

B : arr 배열 내 뒤에서부터 최대부분합

C : arr 배열 내 최대부분합

D : arr 배열 총합

 

이라고 하자.

정답이 가능한 경우는 위와 같다.

위 그림에서 한 칸이 배열 arr이라고 했을 때

1. B D D D A

2. D D D D D

3. C

4. B A

 

이 네가지 중 최대 값이 정답이 된다.

 

시간복잡도는 O(arr.length + k)

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/1191.%20K-Concatenation%20Maximum%20Sum.cpp