首页 > 专题系列 > Java解POJ > POJ 2593 Max Sequence [解题报告] Java
2013
11-11

POJ 2593 Max Sequence [解题报告] Java

Max Sequence

问题描述 :

Give you N integers a1, a2 … aN (|ai| <=1000, 1 <= i <= N).



You should output S.

输入:

The input will consist of several test cases. For each test case, one integer N (2 <= N <= 100000) is given in the first line. Second line contains N integers. The input is terminated by a single line with N = 0.

输出:

For each test of the input, print a line containing S.

样例输入:

5
-5 9 -5 11 20
0

样例输出:

40

解题代码:

//* @author 
import java.util.Scanner;
public class Main{
 public static void main(String args[]){
     
  int data[]=new int[100000];
  int dp[]=new int[100000];   
  int n;
  Scanner in=new Scanner(System.in);   
    while((n=in.nextInt())!=0){   
           
        int sum = 0, tmp = -999999999;   
        for(int i = 0; i < n; i++){   
            data[i]=in.nextInt();   
            sum += data[i];   
            if(sum > tmp)   
                tmp = sum;   
            dp[i] = tmp;   
            if(sum < 0)   
                sum = 0;   
        }   
        sum = 0;   
        int ans = -999999999;   
        for(int i = n-1; i > 0; i--){   
            sum += data[i];   
            if(dp[i-1]+sum > ans)   
                ans = dp[i-1]+sum;   
            if(sum < 0)   
                sum = 0;   
        }   
        System.out.printf("%d\n", ans);   
    }   
 }
}

  1. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。

  2. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。