how to remove : java.lang.OutOfMemoryError

Question

I am solving this question (Stated below with solution (including dp)) , I am getting java.lang.OutOfMemoryError error . I have learned that dp removes unnecessary calculations so i have applied dp also , but then why i am getting this error can we optimize better than dp also ? or i am doing something wrong as the solution runs for small input?

Problem Statement

Your algorithms have become so good at predicting the market that you now know what the share price of Wooden Orange Toothpicks Inc. (WOT) will be for the next N days.

Each day, you can either buy one share of WOT, sell any number of shares of WOT that you own, or not make any transaction at all. What is the maximum profit you can obtain with an optimum trading strategy?

Input

The first line contains the number of test cases T. T test cases follow:

The first line of each test case contains a number N. The next line contains N integers, denoting the predicted price of WOT shares for the next N days.

Output

Output T lines, containing the maximum profit which can be obtained for the corresponding test case.

Constraints

1 <= T <= 10 1 <= N <= 50000

All share prices are between 1 and 100000

MY solution

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);
}
}

Answer 1

As mention in the comment, for your dp table, you are using 50000*50000*64 bit memory (long[][]dp), which is around 20 GB, and it is too large for any personal computer.

The problem can be solved in a much easier manner.

For set of n days, assume that in day i, we have the largest price for WOT, so, to make the largest profit, we need to buy WOT from day 0 to day i - 1, and sell all of them in day i. From day i + 1 onward, we can follow the same strategy, which we will result us the maximum profit.

Space complexity for this solution is O(n), and time complexity is O(n log n) if implemented properly.

Pseudo-code:

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;