Geek asks and answers

Search for the number of possible sequences in an array with additional conditions

There is a sequence {a1, a2, a3, a4, ..... aN}. Mileage is a strictly strictly increasing or strictly decreasing continuous part of a sequence. For instance. If we have the sequence {1,2,3,4,7,6,5,2,3,4,1,2} We have 5 possible runs {1,2,3,4,7}, {7 , 6,5,2}, {2,3,4}, {4,1} and {1,2}.

Given the four numbers N, M, K, L. Count the number of possible sequences of N numbers that have exactly M runs, each of the numbers in the sequence is less than or equal to K, and the difference between adjacent numbers is less than L

A question was asked during the interview.

I could only think of a brute force solution. What is an effective solution to this problem?

+5
source share
3 answers

Use dynamic programming. For each number in the substring, individual values ​​of the maximum increasing and maximum decreasing subsequences are stored. When you gradually add a new number at the end, you can use these counts to update the counters for the new number. Difficulty: O (n ^ 2)

0
source

. # (N, M) (, K L , , ). A (N, M; a) D (N, M, a), A , D , a - .

Express # (N, M) A (N, M; a) D (N, M; a) ( ). , (, A (N, M; a) = D (N, M; Ka)), , .

A (N, M; a) A (N-1, M; w), A (N-1, M-1; x), D (N-1, M; y) D (N-1, M-1; z). , N-1 , , a . , , .

. , L ( , L) K ( ).

, , A (1, 1; a) = 1, A (1, x > 1; a) = 0 ( D).

, , , ( ).

0

, " ", " , N, M, K, L"? . , , . , .

- . :

  • , <= K, , <= L.
  • .
  • Find the intersection of values ​​in these 2 data structures; these will be indices of interesting places to start your search for runs.
  • Take a look at each of the interesting places.

Until someone demonstrates otherwise, this is the most effective solution.

-1
source

More articles:


All Articles