杭电oj1003java实现

问题描述

给定序列a [1]，a [2]，a [3] … a [n]，您的工作是计算子序列的最大和。 例如，给定（6，-1,5,4，-7），此序列中的最大和为6 （-1） 5 4 = 14。

输入

输入的第一行包含一个整数T（1 <= T <= 20），这意味着测试用例的数量。 然后是T行，每行以数字N开头（1 <= N <= 100000），然后是N个整数（所有整数都在-1000和1000之间）。

产量

对于每个测试用例，你应该输出两行。 第一行是“Case＃：”，＃表示测试用例的编号。 第二行包含三个整数，序列中的最大和，子序列的起始位置，子序列的结束位置。 如果有多个结果，则输出第一个结果。 在两种情况之间输出一个空行。

示例输入

2

5 6 -1 5 4 -7

7 0 6 -1 1 -6 7 -5

示例输出

Case 1:

14 1 4

Case 2:

7 1 6

分析

求最大子序列问题。核心就是先算出每一个以第i个元素结尾的最大序列。这个以第i个结尾的最大序列有两种可能，第一，以i-1个结尾的最大序列加上第i个元素，或者是第i个元素本身，要判断大小，在确定值的时候 顺便确定头和尾。在从i个中找出最大序列。详细看代码。

import java.util.Scanner;
public class 杭电1003dp {
  public static void main(String[] args)
 {
   Scanner sc=new Scanner(System.in);
   int t=sc.nextInt();
   int c[][]=new int [t][3];
   for(int q=0;qdp[i-1] a[i]) {start=i;}//如果当前节点大，头信息更改
       if(dp[i]>dpmax) {valuestart=start;valuend=end;dpmax=dp[i];}//一定要有等于号
     }
     c[q][0]=dpmax;//储存结果
     c[q][1]=1 valuestart;
     c[q][2]=valuend 1; 
   }
   for(int i=0;ij?i:j;
  }
}