I_Hate_Swaps's blog

A Subsequence Problem
By I_Hate_Swaps, history, 3 years ago, In English

Please help me to solve this problem :

Given an array A containing n non-negative integers, check if there exists any subsequence of length exactly equal to K such that its sum is atleast S

Constraints:

1<=n<=1e5

1<=k<=n

0<=A[i]<=1e9

0<=S<=1e11

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Just check for a subsequence with length K and highest sum. i.e check if the largest k numbers have a sum greater than S.

→ Reply