杭电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;
	}
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
 

文章来源: bigsai.blog.csdn.net，作者：Big sai，版权归原作者所有，如需转载，请联系作者。

原文链接：bigsai.blog.csdn.net/article/details/79627270