一个简单的算法题（杭电ACM Problem10003）,该怎么解决

一个简单的算法题（杭电ACM Problem10003）
下面是我的答案，提交后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;} 

 

查看更多 下一篇