CP Practices (GPT Created)

function maxSubArray(nums) {
  let maxSum = nums[0]; // Initialize maxSum to the first element
  let currentSum = nums[0]; // Initialize currentSum to the first element

  for (let i = 1; i < nums.length; i++) {
    // Update currentSum to be the maximum of the current element or the sum of currentSum + current element
    currentSum = Math.max(nums[i], currentSum + nums[i]);

    // Update maxSum if the currentSum is greater than maxSum
    maxSum = Math.max(maxSum, currentSum);
  }

  return maxSum;
}

// Example usage:
const nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
//console.log(maxSubArray(nums)); // Output: 6

/*-------------------------------------------------------------*/

function longestCommonSubsequence(text1, text2) {
  const m = text1.length;
  const n = text2.length;

  // Create a 2D array to store the length of LCS for substrings
  const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
  console.debug(dp);

  // Build the dp array
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (text1[i - 1] === text2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1; // Characters match, extend the subsequence
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); // Take the max from previous subproblems
      }
    }
  }
  console.debug(dp);

  // The bottom-right corner of the dp array will have the length of the LCS
  return dp[m][n];
}

// Example usage:
const text1 = "abcde";
const text2 = "ace";
// console.log(longestCommonSubsequence(text1, text2)); // Output: 3 (LCS is "ace")

/*-------------------------------------------------------------*/

function fib(n, memo = {}) {
  console.debug(n, memo);

  // Base cases
  if (n <= 1) return n;

  // If the value is already calculated, return it from the memo
  if (n in memo) return memo[n];

  // Recursively calculate the Fibonacci number and store it in memo
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);

  return memo[n];
}

// Example usage:
// console.log(fib(10)); // Output: 55

/*-------------------------------------------------------------*/

function coinChange(coins, amount) {
  // Initialize dp array where dp[i] is the minimum number of coins to make change for i
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0; // Base case: 0 coins are needed to make amount 0

  console.debug(dp);

  // Update dp array using the coins
  for (let i = 1; i <= amount; i++) {
    for (let coin of coins) {
      console.debug(i, coin);

      if (i - coin >= 0) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
      }

      console.debug(dp);
    }
  }

  // If dp[amount] is still Infinity, it means we cannot make the change with the given coins
  return dp[amount] === Infinity ? -1 : dp[amount];
}

// Example usage:
const coins = [1, 2, 5];
const amount = 11;
console.log(coinChange(coins, amount)); // Output: 3 (11 = 5 + 5 + 1)