### bY_1998's blog

By bY_1998, 5 weeks ago,

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.

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

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

 » 5 weeks ago, # |   +1 You should give the link to the problem.
•  » » 5 weeks ago, # ^ |   0 I would have given if it existed actually its a homework problem from some university's algorithm course
 » 5 weeks ago, # |   +4 Is it from any ongoing contest?
•  » » 5 weeks ago, # ^ |   0 No
•  » » » 5 weeks ago, # ^ |   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).
•  » » » » 5 weeks ago, # ^ |   +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#include #include #include #include #include // This is the quick-select from https://cp-algorithms.com/sequences/k-th.html template T order_statistics (std::vector a, unsigned n, unsigned k) { using std::swap; for (unsigned l=1, r=n; ; ) { if (r <= l+1) { // the current part size is either 1 or 2, so it is easy to find the answer if (r == l+1 && a[r] < a[l]) swap (a[l], a[r]); return a[k]; } // ordering a[l], a[l+1], a[r] unsigned mid = (l + r) >> 1; swap (a[mid], a[l+1]); if (a[l] > a[r]) swap (a[l], a[r]); if (a[l+1] > a[r]) swap (a[l+1], a[r]); if (a[l] > a[l+1]) swap (a[l], a[l+1]); // performing division // barrier is a[l + 1], i.e. median among a[l], a[l + 1], a[r] unsigned i = l+1, j = r; const T cur = a[l+1]; for (;;) { while (a[++i] < cur) ; while (a[--j] > cur) ; if (i > j) break; swap (a[i], a[j]); } // inserting the barrier a[l+1] = a[j]; a[j] = cur; // we continue to work in that part, which must contain the required element if (j >= k) r = j-1; if (j <= k) l = i; } } struct Amorphous { // Idea: M. Douglas McIlroy // Generally breaks single-pivot quicksort // See https://www.cs.dartmouth.edu/~doug/aqsort.c int uid; std::shared_ptr val; std::shared_ptr cprCt; static int count; static int evap; static long long overallCprCt; Amorphous() :uid { count++ }, val { new int { std::numeric_limits::max() } }, cprCt { new int { 0 } } {} int freeze() const { if (*val >= evap) *val = evap++; return *val; } bool operator < (const Amorphous& o) const { ++overallCprCt; if (std::min(*val, *o.val) < evap) return *val < *o.val; if (++*cprCt < ++*o.cprCt) { ++*cprCt; *o.val = evap++; } else { ++*o.cprCt; *val = evap++; } return *val < *o.val; } bool operator > (const Amorphous& o) const { return o < *this; } }; int Amorphous::count; int Amorphous::evap; long long Amorphous::overallCprCt; struct Int { int v; Int(int val) :v { val } {} static long long overallCprCt; bool operator < (Int o) const { ++overallCprCt; return v < o.v; } bool operator > (Int o) const { return o < *this; } }; long long Int::overallCprCt = 0; int main() { using namespace std; ios::sync_with_stdio(false); int n; cin >> n; assert(n >= 2); vector v; v.reserve(n+1); for (int i = 0; i <= n; ++i) v.emplace_back(); order_statistics(v, n, n - 2); cout << "total comparisons: " << Amorphous::overallCprCt << '\n'; cout << "show input?\n"; int flag; cin >> flag; if (!flag) return 0; vector s; s.reserve(n+1); for (Amorphous& x : v) s.emplace_back(x.freeze()); order_statistics(s, n, n - 2); assert(Int::overallCprCt == Amorphous::overallCprCt); for (Int x : s) cout << x.v << ' '; cout << '\n'; return 0; } 
•  » » » » » 5 weeks ago, # ^ |   0 Thanks a lot!!!!