https://www.geeksforgeeks.org/maximum-sum-increasing-subsequence-dp-14/

maximum-sum-increasing-subsequence.js

// https://www.geeksforgeeks.org/maximum-sum-increasing-subsequence-dp-14/
// https://practice.geeksforgeeks.org/problems/maximum-sum-increasing-subsequence/0

function maxSumIncreasingSubsequence(arr) {
  const len = arr.length;
  let idx;
  let idx2;
  let resSum = [...arr];
  // Loop through all members
  for (idx = 1; idx < len; idx++) {
    let maxSoFar = 0;
    //  Compare with all the previous members
    for(idx2 = 0; idx2 < idx; idx2++) {
      if (arr[idx2] < arr[idx] && arr[idx2] > maxSoFar) {
        maxSoFar = arr[idx2];
        resSum[idx] += arr[idx2];
      }
    }
  }
  return Math.max(...resSum);
}

const ex1 = [1,101,2,3,100,4,5];
const resEx1 = maxSumIncreasingSubsequence(ex1);
console.log(resEx1, resEx1 === 106);

const ex2 = [3,4,5,10];
const resEx2 = maxSumIncreasingSubsequence(ex2);
console.log(resEx2, resEx2 === 22);

const ex3 = [10,5,4,3];
const resEx3 = maxSumIncreasingSubsequence(ex3);
console.log(resEx3, resEx3 === 10);

const practice1 = '1 101 2 3 100 4 5'.split(' ').map((char) => Number(char));
const resPractice1 = maxSumIncreasingSubsequence(practice1);
console.log(resPractice1, resPractice1 === 106);

const practice2 = '10 5 4 3'.split(' ').map((char) => Number(char));
const resPractice2 = maxSumIncreasingSubsequence(practice2);
console.log(resPractice2, resPractice2 === 10);