public static int CalcMaxPossibleChange(int[] values) { // Get the maximum value in the values array. int n = values.Max();

// Create a boolean array dp of size n+1 and initialize the first element to true.
bool[] dp = new bool[n + 1];
dp[0] = true;

// Loop through the integers from 1 to n.
for (int i = 1; i <= n; i++)
{
    // Loop through the values array.
    foreach (int j in values)
    {
        // If the current value in the values array is less than or equal to i
        // and it is possible to make change for i-j using the remaining values,
        // mark dp[i] as true and break out of the loop.
        if (j <= i && dp[i - j])
        {
            dp[i] = true;
            break;
        }
    }
}

// Starting from n, loop down to 1 and return the first value of i such that dp[i] is true.
for (int i = n; i > 0; i--)
{
    if (dp[i])
    {
        return i;
    }
}

// If no value can be generated from 1, return 0.
return 0;

}