【求助】帮忙分析一下内存消耗

Question

代码如下，有道的第三题 ，各种MLE， 内存用了234440kB，不知道在哪里开销比较大，求大牛不吝赐教~
public class Main {
static int data[] = new int[50001]; static int ff[] = new int[50001]; static int bb[] = new int[50001]; static int solve(int n) {
int s = 0;
for (int i = 0; i < n; ++i) {
if (i > 0)
ff[i] = ff[i - 1];
else
ff[i] = 0;
if (s < 0)
s = 0;
s += data[i];
ff[i] = ff[i] > s ? ff[i] : s;
}
s = 0;
for (int i = n - 1; i >= 0; --i) {
if (i < n - 1)
bb[i] = bb[i + 1];
else
bb[i] = 0;
if (s < 0)
s = 0;
s += data[i];
bb[i] = bb[i] > s ? bb[i] : s;
}
int ans = 0;
for (int i = 0; i < n - 1; ++i)
ans = ans > (ff[i] + bb[i + 1]) ? ans : (ff[i] + bb[i + 1]);
return ans;
} public static void main(String[] args) {
java.util.Scanner sin = new java.util.Scanner(System.in);
int T = sin.nextInt(); while (--T > -1) {
int n = sin.nextInt(); int sum = 0, cnt = 0;
for (int i = 0; i < n; ++i) {
data[i] = sin.nextInt();
sum += data[i];
if (data[i] > 0)
cnt++;
}
if (cnt <= 2) {
System.out.println(sort(n));
continue;
}
int s1 = solve(n);
for (int i = 0; i < n; ++i)
data[i] = -data[i];
int s2 = sum + solve(n);
System.out.println(s1 > s2 ? s1 : s2);
}
} static int sort(int n) {
int ret[] = new int[2];
ret[0] = ret[1] = -10001;
for (int i = 0; i < n; i++)
if (data[i] > ret[0]) {
ret[1] = ret[0];
ret[0] = data[i];
} else if (data[i] > ret[1]) {
ret[1] = data[i];
}
return ret[0] + ret[1];
}
}

Answer 1

3个这么大的数组new int[50001];一个int至少4个字节
3x4x50001byte

Answer 2

static int data[] = new int[50001];
static int ff[] = new int[50001];
static int bb[] = new int[50001];为什么要开放这么大的数组空间？

Answer 3

这个不是这么算的。JVM 初始化默认就要先占用 64MB 的内存，用于堆之用。但是只是先占用着，并不是全部用光了。JVM 需要对这些内存进行初始化工作，因此需要先占用。另外，在线测试平台本身的内存计算方式也是一个问题，如果 JVM 没有设置过 -Xmx 的话，那么其使用的内存数不会超过 64MB。

Answer 4

这个是有道的一道测试题原题如下;【http://poj.youdao.com/practice/I/】
描述
    给一个整数数组A={a1,a2,…an}, 将这个数组首尾相接连成一个环状，它的一个子序列是指这个数组连续的一段，比如a2,a3…ak，或者an,a1…ai。请从这个环上选取两个不重叠的非空子序列，使这两个子序列中的所有数字之和最大。
    在三个样例中分别选取的子序列是:
    样例一: {a1} {a3}
    样例二: {a1} {a3}
    样例三: {a5,a1} {a3}
输入
    输入的第一行包含一个正整数T(1<=T<=40)，表示有T组测试数据。
    接下来每个测试数据包含两行，第一行是一个正整数n(2<=n<=50000), 第二行是用空格隔开的数组A的n个数，依次为a1,a2,…an (|ai|<=10000)。
输出
    每组数据输出一行，包含一个数，即所求的这两个子序列的元素之和。
样例输入    3
    3
    1 -1 0
    4
    1 -1 1 -1
    5
    1 -1 1 -1 1样例输出    1
    2
    3

Answer 5

为什么在线测试平台使用 Java 语言写的程序要比其他语言写的程序时间要高出很多？这大部分的原因在于在线测试平台计时的问题，把 JVM 初始化的时间也全部算到程序计时中去了。如果不算 JVM 初始化的时间，目前的 JVM 已经是高度优化过的，在自己的内容中进行运算。在某些数值类型的计算速度比 C 语言还要快。至于其他数据类型也不至于要比 C 语言慢几十、上百倍的速度。昨天做了一下两道题，我用相同的算法，在 GCC、G++、Java 都写了一遍，时间结果：B: Power           Accepted      276kB      10ms    GCC
B: Power           Accepted      440kB     100ms    G++
B: Power           Accepted    32140kB     850ms    JavaJ: 有“道”难题    Accepted     1236kB     140ms    GCC
J: 有“道”难题    Accepted     2416kB     550ms    G++
J: 有“道”难题    Accepted    56272kB    1550ms    Java

Answer 6

建议做这些题目还是用 C 语言吧，用 C++ 都慢。对于算法来说，要把 Java 版的改为 C 语言版的也是很方便的，最多在 IO 那里处理一下就可以了。

Answer 7

我这道题也用G++写了，用Java写过好多，但没有MLE这么离谱的这是该题的链接
http://poj.youdao.com/practice/I/

Answer 8

不好意思，问一下“MLE”指的是啥？我第一次在这上面写代码。

Answer 9

我给一点优化建议吧。static int data[] = new int[50001];
static int ff[] = new int[50001];
static int bb[] = new int[50001];去掉 static，将其搬入局部变量，数组长度不需要先定死，测试输入中有数据长度，根据这个数值创建数组对象。import java.util.Scanner;public class Main {    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        while(n-- > 0) {
            int[] data = new int[scanner.nextInt()];
            for(int i = 0, k = data.length; i < k; i++) {
                data[i] = scanner.nextInt();
            }
            // 用这个 data 进行运算，算完后直接用 System.out.pintln 输出一组数据的结果
        }
    }
}

Answer 10

我这块试过了，http://poj.youdao.com/practice/I/ 你能用Java写一下吗