CPP one test case not accepting


#1

Solution::solve(vector &price, int k)
{
long long int n=price.size();
long long int profit[k+1][n+1];
for(int i=0;i<=k;i++)
{
profit[i][0]=0;
}
for(long long int i=0;i<n;i++)
{
profit[0][i]=0;
}
for(long long int i=1;i<=k;i++)
{
for(long long int j=1;j<n;j++)
{
long long int ma=INT_MIN;
for(long long int m=0;m<j;m++)
{
ma=max(ma,price[j]-price[m]+profit[i-1][m]);
}
profit[i][j]=max(profit[i][j-1],ma);
}
}
return profit[k][n-1];
}
Test case:
32 19230 13765 6863 3840 8367 15603 16327 15140 5582 12937 9472 14190 9541 4126 2757 400 19685 15908 4929 18136 16050 6622 13439 265 5846 3188 8756 4960 18781 11139 5152 12314
100000089

Runtime Error.

Your submission stopped because of a runtime error. ex: division by zero, array index out of bounds, uncaught exception.


#2

if(b>A.size())
then we just copy the remaining values…
so just use b = min(b, A.size()) before declaring the 2D array.


#3

Thank you, it worked!


#4
int find(vector<int> &A, int k, int n, vector<vector<int>> &t)

{
int p = 0;
//cout << "n: " << n << endl;
if(n <= 0 || k == 0)
{
return 0;
}
if(t[n][k] != -1)
{
return t[n][k];
}
for(int j = 0; j < n; j++)
{
p = A[n] - A[j] + find(A,k-1,j,t);
}

p = max(p,find(A,k,n-1,t));
t[n][k] = p;
cout << "n: " << A[n] << "   p: " << p << endl;
return p;

}
int Solution::solve(vector &A, int B)
{
int n = A.size();
vector<vector> t(n+1);
for(int i = 0; i <= n; i++)
{
t[i] = vector(B+1,-1);
}
cout << “calling…” << endl;
return find(A,B,n-1,t);
}

What is wrong with the above code? My approach is also same as yours, just I’m using a recursive solution.


#5

B = min(B,A.size()/2)
You cannot complete more transactions than the half size of the array in any case.