PKU ACM 2479-Maximum sum

동적 계획 문제
http://acm.pku.edu.cn/JudgeOnline/problem?id=2479
 
Maximum sum
Time Limit: 1000MS
 
Memory Limit: 65536K
Total Submissions: 17327
 
Accepted: 5239
Description
Given a set of n integers: A={a1, a2,..., an}, we define a function d(A) as below:
여기 서 공식 이 보이 지 않 는 것 은 바로 배열 A 의 두 단락 배열 의 합 의 를 구 하 는 것 이다.
 
Your task is to calculate d(A).
Input
The input consists of T(<=30) test cases. The number of test cases (T) is given in the first line of the input.
Each test case contains two lines. The first line is an integer n(2<=n<=50000). The second line contains n integers: a1, a2, ..., an. (|ai| <= 10000).There is an empty line after each case.
Output
Print exactly one line for each test case. The line should contain the integer d(A).
Sample Input

1

10
1 -1 2 2 3 -3 4 -4 5 -5

Sample Output

13

Hint
In the sample, we choose {2,2,3,-3,4} and {5}, then we can get the answer.
Huge input,scanf is recommended.
문제 풀이 보고서:
배열 의 중성자 배열 의 최대 화 를 구 하 는 것 은 프로 그래 밍 의 아름다움 에 있어 서 언급 되 었 다.그러나 여기 서 요구 하 는 것 은 두 단락 의 배열 의 합 의 최대 치 입 니 다. 두 번 째 로 옮 겨 다 닐 때 첫 번 째 로 옮 겨 다 닐 때 각 수의 이전 배열 의 중성자 배열 의 최대 와 두 번 째 로 옮 겨 다 닐 때 각 수의 다음 배열 의 중성자 배열 의 최대 화 를 구하 고 그 전의 하위 배열 의 최대 와 더 해 마지막 최대 치 를 얻 습 니 다.첫 번 째 는 앞에서, 두 번 째 는 뒤에서 앞으로 옮 겨 다 닌 다.
처음
start [i]: a [i] 앞 에는 반드시 a [i] 의 하위 배열 의 최대 합 이 포함 되 어 있 습 니 다.
all [i]: a [i] 앞의 하위 배열 의 최대 합.
두 번 째 옮 겨 다 니 며 nStart, nall, 최대 값 = nall + all [i - 1] 을 직접 계산 합 니 다.
복잡 도 분석, O (n)
#include using namespace std; #define N -500000001 int returnmax(int a, int b) { return a>b? a: b; } int main() { int caseNum; cin >> caseNum; while(caseNum--) { int max=N; int n; cin >> n; int *a = new int[n]; int *start = new int[n]; int *all = new int[n]; int nstart; int nall; for(int i = 0; i < n; i++) { scanf("%d",&a[i]); if(i>0) { start[i]=returnmax(a[i],start[i-1]+a[i]); all[i]=returnmax(all[i-1],start[i]); } else { start[i]=a[i]; all[i]=a[i]; } } for(int i=n-1;i>0;i--) { if(i==n-1) { nstart=a[i]; nall=a[i]; max=returnmax(max,nall+all[i-1]); } else { nstart=returnmax(a[i],nstart+a[i]); nall=returnmax(nall, nstart); max=returnmax(max,nall+all[i-1]); } } printf("%d/n",max); delete [] a; delete [] start; delete [] all; } }