educative.io

Educative

Brute Force Solution without using sum as an argument

int findMSISRecursive(const vector<int> &nums, int prev, int current) {
if (current == nums.size()) {
    return 0;
}

int sub1 = 0;
if (prev == -1 || nums[current] > nums[prev]) {
    sub1 = nums[current] + findMSISRecursive(nums, current, current + 1);
}

int sub2 = findMSISRecursive(nums, prev, current + 1);

return max(sub1, sub2);

}


Course: https://www.educative.io/courses/grokking-dynamic-programming-patterns-for-coding-interviews
Lesson: Maximum Sum Increasing Subsequence - Grokking Dynamic Programming Patterns for Coding Interviews