[leetcode][1005] Maximize Sum Of Array After K Negations

문제 : https://leetcode.com/problems/maximize-sum-of-array-after-k-negations/

 

---

배열을 오름차순 정렬한다.

음수이고 K가 양수이면 -1을 곱해서 sum을 더한다(K도 1씩 감소). 그러면서 마지막으로 -1을 곱한 수를 따로 저장해둔다.

양수이고 K가 양수이면 K를 2로 나눈 나머지를 구한다. 나머지가 1이라면 양수에 -1을 곱해야 하는데 이때, 마지막으로 -1을 곱한 음수와 비교해야 한다.

예를 들어, [-8,-5,-3,-5,-2,3] 이고 K가 6일 때, 마지막으로 -1을 곱한 음수는 -2이고. -1을 곱할 양수를 3이라고 하자.

총합은 가장 작은 양수인 3을 음수로 만드는 것보다 -2를 양수로 만드는 것이 더 크다.

그러므로 -2는 양수로 만들지 않고 3을 음수로 만들지 않는다.

따라서 정답 배열은 [8,5,3,5,-2,3]가 되고 총합은 22이다.

시간복잡도는 정렬하는데 가장 많은 시간이 드므로 배열 길이를 N이라고 했을 때, O(NlogN)이다.

---

소스코드 : https://gist.github.com/fpdjsns/490b29a87a3188463688020726705547