bY_1998's blog

By bY_1998, 3 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

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

You should give the link to the problem.

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

Is it from any ongoing contest?

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

    No

    • »
      »
      »
      3 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).

      • »
        »
        »
        »
        3 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