How should I practice Maximum Sum Increasing Subsequence?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Microsoft onsite interview problems in FastPrep.

Is Maximum Sum Increasing Subsequence associated with Microsoft?

FastPrep tags this as a Microsoft onsite interview coding practice problem when the problem catalog has that company and stage context.

Maximum Sum Increasing Subsequence

Microsoft● MediumNEW GRADONSITE INTERVIEW

Learn

Problem statement

Given a nonempty integer array nums, return the maximum possible sum of a strictly increasing subsequence.

A subsequence preserves the original index order and may omit values. It must contain at least one value.

Function

maxSumIncreasingSubsequence(nums: int[]) → long

Examples

Example 1

nums = [1,101,2,3,100,4,5]return = 106

The increasing subsequence [1,2,3,100] has sum 106, which is maximal.

Example 2

nums = [4,3,2,1]return = 4

No two values form an increasing subsequence in index order, so the best nonempty choice is [4].

Constraints

1 <= nums.length <= 2000
-10^6 <= nums[i] <= 10^6