연속부분수열을 뒤집어 짝수항의 값이 최대가 되도록 하기

int cal(int * arr, int n)

{

int l = 0; int r = 1;

int cha = 0;

int max=-2000000000;

int temp = 2;

 

for (int i = 0; i < n; i+=2)

{

if (cha < 0)

{

cha = arr[i+1]-arr[i];

}

else

{

cha = cha + arr[i + 1] - arr[i];

}

 

if (cha > max)

{

if (max < 0)

{

l = i;

r = i + 1;

}

else

r += temp;

max = cha;

temp = 2;

}

else

{

temp += 2;

}

}

 

int loop = (r - l + 1)/2;

for (int i = 0; i < loop; i++)

{

temp = arr[l+i];

arr[l + i] = arr[r - i];

arr[r - i] = temp;

}

 

max = 0;

for (int i = 0; i < n; i +=2)

max += arr[i];

 

return max;

}

/////////////////////////////////////////

 해당 부분에서 실행하는 연속부분수열은 바로 arr[i+1]-arr[i]의 차이다. 따라서, 기존의 부분수열을 arr[i+1]-arr[i] 로 대체한다. 이후에는 세 가지 경우의 수가 있다. l의 갱신, r의 2칸 움직임, 어떠한 움직임도 일어나지 않음.

 l가 바뀌기 위해서는 완전히 앞에 끌고가던 수가 음수가 되어, 앞의 수를 버리고 l을 갱신할 필요가 있을 때이다. 따라서 max가 음수가 될 때, l을 i로 갱신시키고 r을 l+1로 놓는다. 반대로 r을 가만히 놓는 경우는, 앞에서 끌고가던 수가 양수는 아니지만 기존의 값보다 작아졌을 때이다. 이 때는, 뒤에 나올 수가 기존의 수보다 더 크게 된다면 이 중간의 모두를 취해야 할 필요가 있지만, 그렇지 않다면 이를 버려야 한다. 따라서 temp를 지정해둬, 만일 r을 옮겨야 할 필요가 있을 경우 적절하게 넘길 수 있도록 2씩 증가시킨다.

 마지막으로 r을 움직여야 할 필요가 있을 떄는, 기존의 수보다 새로 갱신된 cha의 합이 더 클 때이다. 이 때는, 기존의 temp만큼 r을 옮긴다.

 이렇게 l과 r에 숫자를 집어넣으면 arr을 [l+i]와 [r-i]끼리 바꾼 다음, arr[i%2==0]끼리 더하고 나면 의도한 결과값이 나온다.

 

너무 어렵고.