How should I practice Find Number of Good Subsequences 🍅?

Start by reading the full statement, solve the visible examples, then compare the pattern against related infosys online assessment problems in FastPrep.

Is Find Number of Good Subsequences 🍅 associated with infosys?

FastPrep tags this as a infosys online assessment coding practice problem when the problem catalog has that company and stage context.

Problem · Dynamic Programming

Find Number of Good Subsequences 🍅

Learn this problem

● Hard

infosysOA

Problem statement

A positive integer array is removable if it can be reduced to one element by performing the following operation any number of times, possibly zero:

Choose two adjacent values i and j such that i > j.
Remove j and add its value to i.

Here i and j are values, not indices.

An array is good if every contiguous subarray of it is removable.

A proper subsequence selects at least one element while preserving order, but does not select the entire original array. Return the number of non-empty proper subsequences of A that are good, modulo 10^9 + 7.

Function

findNumberOfGoodSubsequences(A: int[]) → int

Examples

Example 1

A = [2, 4, 2, 2]return = 9

For positive values, a selected sequence is good exactly when no two adjacent selected values are equal. There are 9 non-empty proper subsequences of [2, 4, 2, 2] with that property.

Example 2

A = [1, 2, 3]return = 6

All 7 non-empty subsequences have unequal adjacent selected values. The complete subsequence [1, 2, 3] is excluded because only proper subsequences are counted, leaving 6.

Constraints

1 <= A.length
Every value in A is a positive integer.