今天的练习题 - 黑马程序员技术交流社区

import java.util.*;
public class Test8 {
/*
给定K个整数组成的序列{ N1, N2, ..., NK }，“连续子列”被定义为{ Ni, Ni+1, ..., Nj }，其中 1 <= i <= j <= K。
“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 }，
其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序，计算给定整数序列的最大子列和,以及和最大的子列高低位角标
输入格式：
输入第1行给出正整数 K (<= 100000)；第2行给出K个整数，其间以空格分隔。
输出格式：
在一行中输出最大子列和。如果序列中所有整数皆为负数，则输出0。
输入样例：
6
-2 11 -4 13 -5 -2
输出样例：
20 1 3
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
//生产随机数数组
int[] num=new int[20];
for(int i=0;i<20;i++)
{
num[i]=(int)(Math.random()*100)-50;
}
//for(int a:num)
//System.out.print(a+" ");
// 常见用于储存Info对象的list
ArrayList<Info> al = new ArrayList<Info>();
// 从数组的第一个位置开始遍历
for(int i=0;i<num.length;i++)
{
//取的子数组的长度
for(int j=1;j<num.length-i-1;j++)
{
//计算子数组的和
calcul(al,num,i,j);
}
}
System.out.println();
//System.out.println(al);
Info max=al.get(0);
//在list中查找和最小的子数组的信息
for(int i=1;i<al.size();i++)
{
if(al.get(i).a>max.a)
max=al.get(i);
}
System.out.println(max.a+"::"+max.b+"::"+max.c);
}
//用于数组num中从下标a开始的长度为b的子数组的和，并保存到al中
public static void calcul(ArrayList<Info> al,int[] num,int a,int b){
int c=a;
while((c+b)<=num.length)
{
int sum=0;
for(int i=c;i<(c+b);i++)
{
sum+=num[i];
}
al.add(new Info(sum,c,b));
c=c+1;
}
}
}
// 该类中 a代表子数组的和，b代表子数组的第一个下标，c该子数组的长度
class Info
{
public int a;
public int b;
public int c;
Info(int a,int b,int c){
this.a=a;
this.b=b;
this.c=c;
}
}

复制代码