BYR Achieve · 镜像论坛

【问题】poj2479的一个问题？

2017/2/21镜像同步5 回复

倒数第十行：为什么int ret必须初始化为INT_MIN，换成arr[0]就会出错？原题目： Maximum sum Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 39902 Accepted: 12484 Description Given a set of n integers: A={a1, a2,..., an}, we define a function d(A) as below: 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. Source POJ Contest,Author:Mathematica@ZSU 链接：http://poj.org/problem?id=2479 代码： [code] ``` #include<stdio.h> #include<iostream> #include<limits.h> using namespace std; #define MAX 50010 int arr[MAX]; int dp1[MAX]; int dp2[MAX]; int main(){ int cases; //cout<<INT_MIN<<endl; scanf("%d",&cases); while(cases--) { int n; scanf("%d",&n); int arr[n]; for (int i=0; i<n; i++) { scanf("%d",arr+i); } int sum=0; int max = arr[0]; for (int i=0; i<n; i++) {//from 0 to n-1 to build dp1 sum += arr[i]; if (sum > max) max = sum; if (sum < 0) sum = 0; dp1[i] = max;//dp1[i] is the max sum before i; } sum = 0; max = arr[n-1]; for (int i=n-1; i>=0; i--) {//from n-1 to 0 to build dp2 sum += arr[i]; if (sum > max) max = sum; if (sum < 0) sum = 0; dp2[i] = max; } int ret = arr[0];//为什么这里必须是INT_MIN，换成arr[0]就会出错？ for (int i=0; i<n-1; i++){//. int temp = dp1[i] + dp2[i+1]; if (temp > ret) ret = temp; } printf("%d\n",ret); } return 0; } ``` [/code]

订阅后，新回复会通过你的通知中心匿名送达。