fork download
copy 
  1. // CPP program to find largest subarray 
  2. // having sum greater than k. 
  3. #include <bits/stdc++.h> 
  4. using namespace std; 
  5.  
  6. // Comparison function used to sort preSum vector. 
  7. bool compare(const pair<int, int>& a,  
  8.              const pair<int, int>& b) 
  9. { 
  10.     if (a.first == b.first) 
  11.         return a.second < b.second; 
  12.  
  13.     return a.first < b.first; 
  14. } 
  15.  
  16. // Function to find index in preSum vector upto which 
  17. // all prefix sum values are less than or equal to val. 
  18. int findInd(vector<pair<int, int> >& preSum, int n, 
  19.                                             int val) 
  20. { 
  21.  
  22.     // Starting and ending index of search space. 
  23.     int l = 0; 
  24.     int h = n - 1; 
  25.     int mid; 
  26.  
  27.     // To store required index value. 
  28.     int ans = -1; 
  29.  
  30.     // If middle value is less than or equal to 
  31.     // val then index can lie in mid+1..n 
  32.     // else it lies in 0..mid-1. 
  33.     while (l <= h) { 
  34.         mid = (l + h) / 2; 
  35.         if (preSum[mid].first <= val) { 
  36.             ans = mid; 
  37.             l = mid + 1; 
  38.         } 
  39.         else
  40.             h = mid - 1; 
  41.     } 
  42.  
  43.     return ans; 
  44. } 
  45.  
  46. // Function to find largest subarray having sum 
  47. // greater than or equal to k. 
  48. int largestSub(int arr[], int n, int k) 
  49. { 
  50.     int i; 
  51.  
  52.     // Length of largest subarray. 
  53.     int maxlen = 0; 
  54.  
  55.     // Vector to store pair of prefix sum 
  56.     // and corresponding ending index value. 
  57.     vector<pair<int, int> > preSum; 
  58.  
  59.     // To store current value of prefix sum. 
  60.     int sum = 0; 
  61.  
  62.     // To store minimum index value in range 
  63.     // 0..i of preSum vector. 
  64.     int minInd[n]; 
  65.  
  66.     // Insert values in preSum vector. 
  67.     for (i = 0; i < n; i++) { 
  68.         sum = sum + arr[i]; 
  69.         preSum.push_back({ sum, i }); 
  70.     } 
  71.  
  72.     sort(preSum.begin(), preSum.end(), compare); 
  73.  
  74.     // Update minInd array. 
  75.     minInd[0] = preSum[0].second; 
  76.  
  77.     for (i = 1; i < n; i++) { 
  78.         minInd[i] = min(minInd[i - 1], preSum[i].second); 
  79.     } 
  80.  
  81.     sum = 0; 
  82.     for (i = 0; i < n; i++) { 
  83.         sum = sum + arr[i]; 
  84.  
  85.         // If sum is greater than k, then answer 
  86.         // is i+1. 
  87.         if (sum > k) 
  88.             maxlen = i + 1; 
  89.  
  90.         // If sum is less than or equal to k, then 
  91.         // find if there is a prefix array having sum 
  92.         // that needs to be added to current sum to 
  93.         // make its value greater than k. If yes, then 
  94.         // compare length of updated subarray with 
  95.         // maximum length found so far. 
  96.         else { 
  97.             int ind = findInd(preSum, n, sum - k - 1); 
  98.             if (ind != -1 && minInd[ind] < i) 
  99.                 maxlen = max(maxlen, i - minInd[ind]); 
  100.         } 
  101.     } 
  102.  
  103.     return maxlen; 
  104. } 
  105.  
  106. // Driver code. 
  107. int main() 
  108. { 
  109.     int arr[] = { -2, 1, 6, -3 }; 
  110.     int n = sizeof(arr) / sizeof(arr[0]); 
  111.  
  112.     int k = 5; 
  113.  
  114.     cout << largestSub(arr, n, k); 
  115.     return 0; 
  116. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2
https://ideone.com/Ff3CcO
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!