진귀한 별미

면접 대비

시간 제한1초메모리 제한128 MB

요약
음식 가치가 나열된 수열에서 이웃한 두 위치를 함께 고르지 않으면서 고른 값들의 합이 최대가 되도록 선택한다.
난이도

보통10점 중 4점

유형
동적 계획법, 배열, 그리디, 구현
정답자
아직 제출이 없습니다

문제

시간 여행은 몹시 피곤한 일이라 금세 배가 고파집니다. 다행히 시대마다 공룡 고기, 도도새 알, 매머드 우유처럼 진귀한 별미가 가득합니다. 하지만 타임머신에는 냉장고를 실을 공간이 없어서, 팀이 어떤 별미를 먹으려면 그 자리에서 바로 먹어야 합니다. 그런데 한 번 먹으면 너무 배가 불러, 바로 다음 시대에서는 아무것도 먹을 수 없습니다. 각 음식에는 팀이 매긴 가치가 있으며, 목표는 실제로 먹는 음식들의 가치 합을 최대로 만드는 것입니다. 시대를 방문하는 순서는 이미 정해져 있어 바꿀 수 없습니다. 어떤 음식을 먹을지 골라서 얻을 수 있는 가치 합의 최댓값은 얼마일까요?

입력

첫째 줄에 데이터 집합의 개수 KK가 주어집니다. 이어서 KK개의 데이터 집합이 다음 형식으로 주어집니다. 각 데이터 집합의 첫째 줄에는 팀이 마주칠 음식의 개수 nn이 주어지며, 1≤n≤500001 \le n \le 50000입니다. 다음 줄에는 음식의 가치를 나타내는 nn개의 정수 viv_i가 주어지며, 1≤vi≤10001 \le v_i \le 1000입니다. 나열된 viv_i의 순서는 팀이 음식을 마주치는 순서와 같습니다.

출력

각 데이터 집합마다 먼저 Data Set x: 를 한 줄에 출력합니다. 여기서 xx는 데이터 집합의 번호로 1부터 시작합니다. 다음 줄에는 팀이 얻을 수 있는 가치 합의 최댓값을 출력합니다. 서로 다른 데이터 집합 사이에는 빈 줄을 하나 넣어 구분합니다.

예제3

  1. 예제 1

    입력
    2
3
3 8 4
4
12 8 9 10
    예상 출력
    Data Set 1:
8

Data Set 2:
22

  2. 예제 2

    입력
    1
1
5
    예상 출력
    Data Set 1:
5

  3. 예제 3

    입력
    3
1
7
2
5 5
3
1 2 3
    예상 출력
    Data Set 1:
7

Data Set 2:
5

Data Set 3:
4