import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
int count=scan.nextInt();
int[] result=new int[3*count];
for(int i=0;i<count;i++){
int a=scan.nextInt();
int[] a1=new int[a];
for(int j=0;j<a;j++){
a1[j]=scan.nextInt();
}
int[] b=maxSubArraySum3(a1);
for(int k=0;k<b.length;k++){
result[i*3+k]=b[k];
}
}
for(int k=1;k<count;k++){
System.out.println("Case "+k+":");
System.out.println(result[k*3-3]+" "+result[k*3-2]
+" "+result[k*3-1]);
System.out.println();
}
System.out.println("Case "+count+":");
System.out.println(result[count*3-3]+" "+result[count*3-2]
+" "+result[count*3-1]);
}
static int[] maxSubArraySum(int[] a){
int sum=0;
int mStart = 0,mEnd = 0;
for(int start=0;start<a.length;start++){
for(int end=start;end<a.length;end++){
int thissum=0;
for(int index=start;index<=end;index++){
thissum+=a[index];
}
if(thissum>sum){
sum=thissum;
mStart=start;
mEnd=end;
}
}
}
return new int[]{sum,mStart+1,mEnd+1};
}
static int[] maxSubArraySum2(int[] a){
int sum=0;
int mStart = 0,mEnd = 0;
for(int start=0;start<a.length;start++){
int thissum=0;
for(int end=start;end<a.length;end++){
thissum+=a[end];
if(thissum>sum){
sum=thissum;
mStart=start;
mEnd=end;
}
}
}
return new int[]{sum,mStart+1,mEnd+1};
}
static int[] maxSubArraySum3(int[] a){
int thissum=0;int maxsum=0;int start=0;int end=0;
for(int j=0;j<a.length;j++){
thissum+=a[j];
if(thissum<0){
thissum=0;
start=j+1;
}else if(thissum>maxsum){
maxsum=thissum;
end=j;
}
}
return new int[]{maxsum,start+1,end+1};
}
}
求连续子序列的最大值
最后编辑于 :
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
- 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
推荐阅读更多精彩内容
- 算法是我最头疼的问题,经常被问到就懵逼,但是后来一想就能想起来,也是没那么能难,人啊就是要多总结,人类的进步就是因...
- MVC 模型设计 contrl -> 'model'skin -> 'view'skin -> 'controle...