길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아닌, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할때, 위치에 상관없이 묶을 수 있다.
하지만 자기 자신을 묶는 것은 불가능
예를 들면, 어떤 수열이 {0, 1, 2, 4, 3, 5}일 때, 그냥 이 수열의 합을 구하면 0+1+2+4+3+5 = 15이다. 하지만, 2와 3을 묶고, 4와 5를 묶게 되면, 0+1+(23)+(45) = 27이 되어 최대가 된다.
문제의 입력은 N → 50 따라서 시간복잡도를 따질 필요는 없음
수열의 모든 수는 단 한번만 묶거나, 아니면 묶지 않아야한다.
처음 아이디어는 내림차순 정렬 후 리스트에 하나씩 넣어 주다가 1을 포함해 더 작은 수가 나오면 또 다른 배열에 저장을 하면 7,6,5,4,3,2,1,0 이라는 숫자가 있을 경우
[7,6,5,4,3,2] , [ 1 , 0 ] 이렇게 저장 된다 이 경우
7*6 + 5 * 4 + 3 * 2 + 1 + 0이렇게 앞의 배열은 서로 곱하고 뒤에 배열은 더하면 제일 큰 숫자를 쉽게 뽑을 수 있을 거라 생각하고(엥 문제가 골드4치고 왜 이렇게 쉽지라고 생각 했지만)
→ 하지만 문제는 0과 -6이 들어왔을 경우는 오히려 두 개를 곱해주는 게 더 큰 수를 만들 수 있음.
또한 음수 두 개는 곱해야 양수가 나오기 때문에 음수는 또 따로 고려해야 함
따라서 음수를 저장하는 배열 , 양수를 저장하는 배열, 1의 숫자 이렇게 각각 상황을 나눠서(그리디)
음수는 내림차순으로 작은 수부터(-6,-5,-4)
양수는 오름차순으로 큰 수부터 (6,5,4) 정렬을 해서 내려가면 결국 양수는 위에서 생각한 아이디어 대로 적용이 되고 음수의 경우 (-6,-5,0)일 경우 30+0 , (-6,0) 일 경우 -6*0 이런식으로 각각 쉽게 처리를 해줄 수 있음
정렬이 되어 있는 입력(최악) → O(n^2)
평균적으로 O(nlogn)