Subsequence having maximum sum

Revision en1, by starboy_9879, 2020-05-05 08:59:06

We have an array of n elements (1 <= n <= 60) We have to determine whats the maximum sum subsequence possible that is less than or equal to a value k (1 <= k <= 10^18). At most 15 of the elements in array, either a[i] >= 2*a[j] or a[j] >= 2*a[i] where j is not equal to i (1 <= a[i] <= 10^17)

This problem was asked in Visa OA and later also in Expedia OA and both the times I couldn't manage to get all test cases passes. The constraints are very big for any regular knapsack approach to work. I thought of dividing the array such that first one will have all those at most 15 elements which shows that mentioned property and rest are the regular ones, since 15 is very less we can use something like bitmasking, so choosing k1 from that set and rest k-k1 from other set. But I couldn't make this idea work it will end up a bruteforce maybe I'm missing some observation. Please help

Tags increasing subsequence, #greedy, #dynamic programing, divide and conquer

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English starboy_9879 2020-05-05 08:59:06 918 Initial revision (published)