转载声明：原文转自http://www.cnblogs.com/xiezie/p/5502855.html
第一、二次的思路都是穷举；
第一次的实现是用二维数组；
import java.util.*;
import java.io.*;
public class Main{
public static void main(String[] arg){
Scanner scan = new Scanner(new BufferedInputStream(System.in));
int n = scan.nextInt();
int l = n;
while(n!=0){
int m = scan.nextInt();
int[] a = new int[m];
int len = 0;
for(int i = 0 ; i != m ; i ++){
a[i] = scan.nextInt();
len = len + i + 1;
}
int[] sum = new int[len];
for(int i = 0 ; i != m ; i ++ ){
int h = 0;
for(int g = 0 ; g != i+1 ; g ++ ){
h+=g;
}
for(int j = i ; j != m ; j ++ ){
for(int k = i ; k != j+1 ; k ++ ){
sum[m*i+j-h] = sum[m*i+j-h] + a[k];
}
}
}
int max = sum[0];
int maxI = 1,maxJ = 1;
for(int i = 0 ; i != m ; i ++ ){
int h = 0;
for(int g = 0 ; g != i+1 ; g ++ ){
h+=g;
}
for(int j = i ; j != m ; j ++ ){
if(sum[m*i+j-h]>max){
maxI = i+1 ;
maxJ = j + 1;
max = sum[m*i+j-h];
}
}
}
System.out.println("Case " + (l-n+1) + ":");
System.out.println(max + " " + maxI + " " + maxJ);
if(n!=1){
System.out.println();
}
n--;
}
}
}但是：报了Memory Limit Exceeded的错误
第二次的思路是将二维数组转化为一维数组
但是运行效果不好，代码冗长
第三次AC
具体分析这个程序应该怎么更好的实现，在输入时就开始判断最大数
import java.util.*;
import java.io.*;
public class Main{
public static void main(String[] arg){
Scanner scan = new Scanner(new BufferedInputStream(System.in));
int n = scan.nextInt();
int y = n;
while(n!=0){
int m = scan.nextInt();
int l = m ;
int sum = -1001;
int max = -1001;
int maxI = 1;
int maxJ = 1;
int i = 1;
int j = 1;
while(m!=0){
int a = scan.nextInt();
if(sum>=0){
j++;
sum += a ;
}else{
i= l-m+1;
j= l-m+1;
sum = a;
}
if(max<sum){
max = sum;
maxI = i;
maxJ = j;
}
m--;
}
System.out.println("Case " + (y-n+1) + ":");
System.out.println(max + " " + maxI + " " + maxJ);
if(n!=1){
System.out.println();
}
n--;
}
}
}