bY_1998's blog

Is it Possible??
By bY_1998, 4 years ago, In English

Hi I am stuck in a problem which I have written below, I doubt whether there is a linear time algorithm which can solve it , If anyone finds any solution please provide me the solution or give some hints at least.

Thanks in advance!!

============================================================================================================================================================================================================================================

Question:---

You are given an array A1 , A2 , . . . ,An of integers (both positive and negative), and a integer l, 0<l ≤ n. The length of a subsequence is defined as the number of integers in the subsequence. Design a linear time algorithm to find the a maximum sum subsequence of length at most l.

  • Vote: I like it
  • -25
  • Vote: I do not like it

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

You should give the link to the problem.

→ Reply
»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Is it from any ongoing contest?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      If the sub-sequence you want need not be continuous , then the problem is basically telling to find the $$$I^{th}$$$ largest number in the array.

      The only linear time algo I know of for this is https://cp-algorithms.com/sequences/k-th.html . It's average runtime is O(N).

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        This is a quick-select with deterministic pivot selection, which makes it easy to construct inputs* for which it will require $$$\Theta(n^2)$$$ time to execute. Randomizing the pivot selection process can yield $$$O(n)$$$ expected runtime, and using a median-of-medians subroutine to select pivots can yield $$$O(n)$$$ worst-case runtime, albeit with a not-so-appealing constant factor.

        *This construction can even be done by using the routine itself as a black-box and a class whose comparator will make inconvenient decisions for it on-the-fly. Here's a simple C++ program that does just that:

        Example
        → Reply