一个简单的算法题（杭电ACM Problem10003）,该怎么解决
日期：2014-05-20 浏览次数：20954 次
一个简单的算法题（杭电ACM Problem10003）
下面是我的答案，提交后OJ给了我个Time Limit Exceeded，求各位大侠看看能不能给精简下。谢谢各位哥哥姐姐了。（注：开始的数组定义不能改）
------解决方案--------------------
这题要用DP（动态规划）
你的算法时间复杂度为O(n^2)
N最大为100000.你的复杂度为10^10
那面的测评机器10^9大约为1s.
你肯定超时了。
我写过一个C++的代码。
看代码估计你也理解不了。
去查一个解题报告吧。
下面是我的答案，提交后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 100001
using 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;
}
免责声明： 本文仅代表作者个人观点，与爱易网无关。其原创性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺，请读者仅作参考，并请自行核实相关内容。
