Блог пользователя bY_1998

Автор bY_1998, 4 года назад, По-английски

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.

  • Проголосовать: нравится
  • -25
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

You should give the link to the problem.

»
4 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Is it from any ongoing contest?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    No

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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).

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        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