some random dude some random dude - 2 months ago 10
C# Question

Index Outside of Bounds on Stock Maximization Algorithm

I have the following code translated as best I could from Java to C#:

public double maxProfit(double[] prices, int K)
{
if (K == 0 || prices.Length == 0)
{
return 0;
}

var dp = new double[K + 1, prices.Length];

for (int i = 1; i < K + 1; i++)
{
double maxDiff = -prices[0];
for (int j = 1; j < prices.Length; j++)
{
dp[i, j] = Math.Max(dp[i, j - 1], prices[j] + maxDiff);
maxDiff = Math.Max(maxDiff, dp[i - 1, j] - prices[j]);
}
}

printTrans(dp, prices, K);


return dp[K, prices.Length - 1];
}

public void printTrans(double[,] dp, double[] prices, int K)
{
int i = K - 1;
int j = prices.Length;

var priceList = new List<double>();
while (true)
{
if (i == 0 || j == 0)
{
break;
}

if (dp[i, j] == dp[i, j - 1])
{
j = j - 1;
}
else
{
priceList.Add(j);
double maxDiff = dp[i, j] - prices[j];
for (int z = j - 1; z >= 0; z--)
{
if (dp[i - 1, z] - prices[z] == maxDiff)
{
i = i - 1;
j = z;
priceList.Add(j);
break;
}
}
}
}

while (priceList.Count > 0)
{
Console.WriteLine("Buy @ " + prices[priceList.IndexOf(0)]);
Console.WriteLine("Sell @ " + prices[priceList.IndexOf(0)]);
}
}


Error occurs in the second method on lines:

if (dp[i, j] == dp[i, j - 1])


and

for (int z = j - 1; z >= 0; z--)
{
if (dp[i - 1, z] - prices[z] == maxDiff)


I am getting an
Index was outside the bounds of the array
. error. I understand what this error means but I have no clue on my to fix it. It took me quite a bit to understand the first part of this code but for the second part, I am at a loss.

Also what is the C# equivalent of the Java
pollFirst()
method?

Answer

Probably this line is the cause

 public void printTrans(double[,] dp, double[] prices, int K)
        {
            int i = K - 1;
            int j = prices.Length; // <=== this line is the cause

its causing the j to refer an index outside the bounds of the 2D array.

If you have ported from java recheck your java code.

Either make that line

int j = prices.Length - 1;

Or you need to make changes to how you create your array

 var dp = new double[K + 1, prices.Length]; // <-- prices.Length would have to change here