java - 如何删除:java.lang.OutOfMemoryError

我正在解决这个问题（下面用解决方案（包括dp）说明），得到java.lang.OutOfMemoryError错误。我已经了解到dp消除了不必要的计算，所以我也应用了dp，但是为什么我会得到这个错误，我们能比dp优化得更好吗或者我做错了什么，因为解决方案只需要少量的输入？
问题陈述
你的算法已经非常擅长预测市场，以至于你现在知道木制橙色牙签公司（wot）未来n天的股价会是多少。
每天，你可以购买一股WOT股票，出售你拥有的任意数量的WOT股票，或者根本不进行任何交易什么是最大的利润，你可以获得最佳的贸易策略？
输入
第一行包含测试用例的数量t.t测试用例如下：
每个测试用例的第一行包含一个数字N，下一行包含N个整数，表示未来N天WOT股票的预测价格。
输出
输出T线，包含相应测试用例所能获得的最大利润。
约束条件
11所有的股价都在1到10万之间
我的解决方案

import java.util.Arrays;
import java.util.Scanner;

public class Stock_Maximize {
private static int days;
private static long[] a;
private static int t;
private static long[][] dp;

// private static int max;

public static void main(String args[]) {
    Scanner e = new Scanner(System.in);
    t = e.nextInt();
    while (t > 0) {
        days = e.nextInt();
        int m = days;
        // System.out.println(days);
        int i = 1;
        a = new long[days + 1];
        while (m > 0) {
            a[i] = e.nextInt();
            i++;
            m--;
        }
        dp = new long[days + 1][days + 1];
        for (int k = 0; k < days + 1; k++) {
            Arrays.fill(dp[k], -1);
        }
        System.out.println(solve(1, 0));
        t--;
    }
}

private static long solve(int daynumber, int stocks) {
    // TODO Auto-generated method stub
    // System.out.println("vefvvv");
    long x;
    int i = 1;

    if (daynumber == (days + 1)) {
        // System.out.println("daynumber= " + daynumber);
        return 0;
    }
    if (stocks < 0) {
        // System.out.println("***********");
        return 0;
    }
    if (dp[daynumber][stocks] != -1) {
        return dp[daynumber][stocks];
    }
    long z = solve(daynumber + 1, stocks + 1) - a[daynumber];
    // System.out.println("z= " + z);
    long m = solve(daynumber + 1, stocks);
    int d = stocks;
    long max = Long.MIN_VALUE;
    while (d > 0) {
        d = stocks - i;
        x = solve(daynumber + 1, d) + i * a[daynumber];

        i++;
        // System.out.println("x= " + x + "z= " + z + "m= " + m);
        if (max < getmax(x, z, m)) {
            max = getmax(x, z, m);
        }
    }
    dp[daynumber][stocks] = Math.max(max, Math.max(z, m));
    return dp[daynumber][stocks];
}

private static long getmax(long x, long z, long m) {
    // TODO Auto-generated method stub
    return Math.max(Math.max(x, z), m);
}
}

最佳答案

正如评论中提到的，对于您的dp表，您使用的50000*50000*64位内存（long[][]dp）大约为20gb，对于任何个人计算机来说都太大了。
这个问题可以用更简单的方法解决。
对于一组n天，假设在i天，我们的WOT价格最高，因此，为了获得最大的利润，我们需要从0天到i - 1天购买WOT，并在i天出售所有WOT从日后开始，我们可以遵循同样的策略，这将使我们获得最大的利润。
该方法的空间复杂度为O（n），如果实现正确，时间复杂度为O（n log n）。
伪代码：

class WOT{
    int day;
    int price;
}

WOT[]data = new WOT[n];
//Initialize data here
long[]cost = new long[n];
for(int i = 0; i < n; i++)
    cost[i] = data[i].price + (i > 0 ? cost[i - 1] : 0);

sort data based on price
int startDate = 0;
long result = 0;
for(int i = n - 1; i >= 0; i--){
    if(data[i].day > startDate){
          int numberOfDays = data[i].day - startDate;
          result += numberOfDays*data[i].price - (cost[data[i].day - 1] - cost[startDate - 1])
          startDate = data[i].day + 1;
    }
}
print result;

关于java - 如何删除:java.lang.OutOfMemoryError，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/33797285/