下面是我的答案，提交后OJ给了我个Time Limit Exceeded，求各位大侠看看能不能给精简下。谢谢各位哥哥姐姐了。（注：开始的数组定义不能改）
- Java code
import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int num = 0; int max, sum, index, startIndex, endIndex; int array[] = new int[100000]; num = scanner.nextInt(); for (int i = 1; i <= num; i++) { max = 0; index = 0; startIndex = 1; endIndex = 1; sum = 0; while (scanner.hasNext()) { array[index] = scanner.nextInt(); index++; if (array[0] == (index - 1)) break; } max = array[1]; for (int j = 1; j <= array[0]; j++) { sum = 0; for (int m = j; m <= array[0]; m++) { sum = sum + array[m]; if (max <= sum) { max = sum; startIndex = j; endIndex = m; } } } System.out.println("Case " + i + ":"); System.out.println(max + " " + startIndex + " " + endIndex); if (i != num) { System.out.println(); } } }}------解决方案--------------------
这题要用DP（动态规划）
你的算法时间复杂度为O(n^2)
N最大为100000.你的复杂度为10^10
那面的测评机器10^9大约为1s.
你肯定超时了。
我写过一个C++的代码。
看代码估计你也理解不了。
去查一个解题报告吧。
- C/C++ code
#include <iostream>#define N 100001using namespace std;int main(){ int t,t1; cin >> t; t1 = t; while ( t-- ) { int m, i, f[N], n[N], l[N], max = 0, left = 1, right = 1; cin >> m; for ( i = 0; i < m; i++) { cin >> n[i]; } f[0] = n[0]; l[0] = 0; for ( i = 1; i < m; i++) { if( 0 > f[i-1] ) { f[i] = n[i]; l[i] = i; } else { f[i] = f[i-1] + n[i]; l[i] = l[i-1]; } } for ( i = 1,max = f[0]; i < m; i++) { if( f[i] > max) { max = f[i]; left = l[i] + 1; right = i + 1; } } cout <<"Case "<<t1 - t<<":"<<endl; cout << max <<" "<< left <<" "<< right <<endl; if(t != 0 ) { cout << endl; } } return 0;}