### serpent54's blog

By serpent54, history, 4 months ago,

How to think about to write code of finding the longest subarray with sum greater than or equal to k in O(nlogn).

• +3

 » 4 months ago, # | ← Rev. 2 →   0 I don't understand your question. if the sum needs to be greater or equal to $k$, can't you just choose all of the elements in the array?
 » 4 months ago, # |   0 Put all negative integers into an array. Greedily choose all positive integers. Sort negative array by least value. Greedily choose minimum negative integer until you can't anymore.
•  » » 4 months ago, # ^ |   0 I just had updated my question if you know please let me know. thank for giving the answer.
 » 4 months ago, # |   0 Auto comment: topic has been updated by serpent54 (previous revision, new revision, compare).
 » 4 months ago, # | ← Rev. 4 →   0 We will call our array $a$, for every $0 \leq i \leq n - 1$ we keep a number $ps_i = a_0 + a_1 + \dots + a_i$.For any $0 \leq l \leq r \leq n - 1$ we can find $a_l + a_{l + 1} + \dots + a_r$ in $O(1)$ using the fact that its value is equal to $ps_r - ps_{l - 1}$ (if $l = 0$ we dont include $ps_{l - 1}$)Using this we write a function $check(s)$ which will heck all subarrays of size $s$, if there is at least one with sum greater or equal to $k$ it returns 1 and otherwise 0. this will work in $O(n)$.Now we can just do a binary search on the size of the subbarray. thus the time complexity is $O(n \log n)$. code#include using namespace std; const int N = 1e5; int n, k, a[N]; long long ps[N]; bool check(int s) { if (ps[s - 1] >= k) return 1; int l = 1, r = s; while (r < n) { if (ps[r] - ps[l - 1] >= k) return 1; r ++, l ++; } return 0; } int main(){ scanf("%d%d", &n, &k); for (int i = 0; i < n; i ++) { cin >> a[i]; i == 0 ? ps[i] = a[i] : ps[i] = ps[i - 1] + a[i]; } int L = 0, R = n + 1, M; while (R - L != 1) { M = (L + R) / 2; check(M) ? L = M : R = M; } printf("%d", L); return 0; }
•  » » 4 months ago, # ^ |   0 Thanks for answering me.
•  » » 4 months ago, # ^ |   +1 Binary search doesn't work. You're incorrectly assuming that if there exists no good subarray of length $m$, there cannot exist a good subarray with length $\ge m$. This is just not true.Consider the following example: $n = 5$, $k = 50$, $a = [10, 10, 10, 10, 10]$. There exists a single good subarray $a[1:5]$ with length $5$, but your binary search won't find it. Run resultsInput: 5 50 10 10 10 10 10 Output: 0 Expected Output: 5 I'll give you another example. Let $n = 12$, $k = 60$, $a = [-10, -10, 10, 10, 10, 10, 10, 10, -10, 10, -10, -10]$. There are two good subarrays, $a[3:8]$ and $a[3:10]$ with lengths $6$ and $8$, but your binary search will "skip over" the one with length $8$ and only return $6$. Run resultsInput: 12 60 -10 -10 10 10 10 10 10 10 -10 10 -10 -10 Output: 6 Expected Output: 8 Let's actually prove that the problem can't be solved with binary search (at least in the way you did it). Consider the last example I gave. I'll modify your program to print the result of $check(s)$ for all possible $s$. Code#include using namespace std; const int N = 1e5; int n, k, a[N]; long long ps[N]; bool check(int s) { if (ps[s - 1] >= k) return 1; int l = 1, r = s; while (r < n) { if (ps[r] - ps[l - 1] >= k) return 1; r ++, l ++; } return 0; } int main(){ scanf("%d%d", &n, &k); for (int i = 0; i < n; i ++) { cin >> a[i]; i == 0 ? ps[i] = a[i] : ps[i] = ps[i - 1] + a[i]; } /*int L = 0, R = n + 1, M; while (R - L != 1) { M = (L + R) / 2; check(M) ? L = M : R = M; } printf("%d", L);*/ //modifications follow: for (int i = 1; i <= n; ++i) { bool res = check(i); printf("check(%d) = %d\n", i, res); } return 0; } Run resultsInput: 12 60 -10 -10 10 10 10 10 10 10 -10 10 -10 -10 Output: check(1) = 0 check(2) = 0 check(3) = 0 check(4) = 0 check(5) = 0 check(6) = 1 check(7) = 0 check(8) = 1 check(9) = 0 check(10) = 0 check(11) = 0 check(12) = 0 If you anything about binary search, you can see that the function $check(s)$ is not binary searchable.
•  » » » 2 months ago, # ^ |   0 Thanks