FastPrep
Problem · Dynamic Programming

Find Number of Good Subsequences 🍅

● HardinfosysOA

It is given that an array A of length N can be called removable, if it can be turned into an array containing one element by performing the following operations some number of times (possibly zero):

  • Choose two adjacent elements i and j such that i > j
  • Remove j from A, and add j to i

    • Here i and j are values not indices.

    We say that an array is good, if all its subarrays are removable.

    Find the number of good subsequences in a. Since answer can be large, return it modulo 109 +7.

    Examples
    01 · Example 1
    A = [2, 4, 2, 2]
return = 9
    No explanation for now. If you happen to know about it. Pls feel free to lmk! Many thanks in advance!
    02 · Example 2
    A = [1, 2, 3]
return = 6
    No explanation for now. If you happen to know about it. Pls feel free to lmk! Many thanks in advance!
    More infosys problems
    drafts saved locally
    public int findNumberOfGoodSubsequences(int[] A) {
    // write your code here
}
    A[2, 4, 2, 2]
    expected9
    checking account