Stock Maximize Discussions | Algorithms | HackerRank
  • + 3 comments

    Actually I had a workaround for O(N*2) complexity and was able to solve using DP. It is important to notice that J(i,x) is of the form Ax + B, where i is the day, and x is the number of stocks at day i, J(i,x) is the maximum profit that can be made from day i till day N. Since J(i,x) is linear all we need is to evaluate is J(i,0) and J(i,1). So N*2 complexity drops down to 2*N!!

    my code for reference:

    long int **J;
    
    long int InvestReturn(long int i,long int x,long int *p,long int N){
    if (i==N) {
        J[N][x]=0;
        return 0;
    }
    if (J[i][x]!=-1) {
        return J[i][x];
    }
    long int A =InvestReturn(i+1,1,p,N)   -InvestReturn(i+1,0,p,N);
    long int B =InvestReturn(i+1,0,p,N);
    
    if (A-p[i]>0) { //buying one stock is opt.
        J[i][x] = -p[i]+A*(x+1)+B;
        return J[i][x];
    }else{ //selling all x stocks is optimal
        J[i][x] = x*p[i]+B;
        return J[i][x];
    }
    

    }