fork download
copy 
  1. // CPP program to find largest subarray 
  2. // having sum greater than k. 
  3. #include <bits/stdc++.h>
  4. #include <ext/pb_ds/assoc_container.hpp>
  5. #include <ext/pb_ds/tree_policy.hpp>
  6.  
  7.  
  8.  
  9. using namespace std; 
  10. using namespace __gnu_pbds;
  11. typedef cc_hash_table<long long int,string, hash<long long int>> ht;
  12.  
  13.  
  14. typedef cc_hash_table<string,long long int, hash<long long int>> ht1;
  15.  
  16.  
  17. // Comparison function used to sort preSum vector. 
  18. bool compare(const pair<int, int>& a,  
  19.              const pair<int, int>& b) 
  20. { 
  21.     if (a.first == b.first) 
  22.         return a.second < b.second; 
  23.  
  24.     return a.first < b.first; 
  25. } 
  26.  
  27. // Function to find index in preSum vector upto which 
  28. // all prefix sum values are less than or equal to val. 
  29. int findInd(vector<pair<int, int> >& preSum, int n, 
  30.                                             int val) 
  31. { 
  32.  
  33.     // Starting and ending index of search space. 
  34.     int l = 0; 
  35.     int h = n - 1; 
  36.     int mid; 
  37.  
  38.     // To store required index value. 
  39.     int ans = -1; 
  40.  
  41.     // If middle value is less than or equal to 
  42.     // val then index can lie in mid+1..n 
  43.     // else it lies in 0..mid-1. 
  44.     while (l <= h) { 
  45.         mid = (l + h) / 2; 
  46.         if (preSum[mid].first <= val) { 
  47.             ans = mid; 
  48.             l = mid + 1; 
  49.         } 
  50.         else
  51.             h = mid - 1; 
  52.     } 
  53.  
  54.     return ans; 
  55. } 
  56.  
  57. // Function to find largest subarray having sum 
  58. // greater than or equal to k. 
  59. int largestSub(int arr[], int n, int k) 
  60. { 
  61.     int i; 
  62.  
  63.     // Length of largest subarray. 
  64.     int maxlen = 0; 
  65.  
  66.     // Vector to store pair of prefix sum 
  67.     // and corresponding ending index value. 
  68.     vector<pair<int, int> > preSum; 
  69.  
  70.     // To store current value of prefix sum. 
  71.     int sum = 0; 
  72.  
  73.     // To store minimum index value in range 
  74.     // 0..i of preSum vector. 
  75.     int minInd[n]; 
  76.  
  77.     // Insert values in preSum vector. 
  78.     for (i = 0; i < n; i++) { 
  79.         sum = sum + arr[i]; 
  80.         preSum.push_back({ sum, i }); 
  81.     } 
  82.  
  83.     sort(preSum.begin(), preSum.end(), compare); 
  84.  
  85.     // Update minInd array. 
  86.     minInd[0] = preSum[0].second; 
  87.  
  88.     for (i = 1; i < n; i++) { 
  89.         minInd[i] = min(minInd[i - 1], preSum[i].second); 
  90.     } 
  91.  
  92.     sum = 0; 
  93.     for (i = 0; i < n; i++) { 
  94.         sum = sum + arr[i]; 
  95.  
  96.         // If sum is greater than k, then answer 
  97.         // is i+1. 
  98.         if (sum > k) 
  99.             maxlen = i + 1; 
  100.  
  101.         // If sum is less than or equal to k, then 
  102.         // find if there is a prefix array having sum 
  103.         // that needs to be added to current sum to 
  104.         // make its value greater than k. If yes, then 
  105.         // compare length of updated subarray with 
  106.         // maximum length found so far. 
  107.         else { 
  108.             int ind = findInd(preSum, n, sum - k - 1); 
  109.             if (ind != -1 && minInd[ind] < i) 
  110.                 maxlen = max(maxlen, i - minInd[ind]); 
  111.         } 
  112.     } 
  113.  
  114.     return maxlen; 
  115. } 
  116.  
  117.  
  118. int main()
  119. {
  120.       ios_base::sync_with_stdio(false);
  121.     cin.tie(NULL);
  122.  
  123.  
  124.  
  125. 	int t;
  126. 	cin>>t;
  127. 	while(t--)
  128. 	{   
  129. 	    int f=-1;
  130. 	    int n;cin>>n;
  131. 	    string s;
  132. 	    cin>>s;
  133. 	     char c='a';
  134. 	    int i=0;
  135. 	    while(i<26)
  136. 	    {
  137. 	      int arr[n];
  138.  
  139. 	       int j=0;
  140. 	        while(j<n)
  141. 	        {
  142. 	            if(s[j]==c)
  143. 	            {
  144. 	                arr[j]=1;
  145. 	            }
  146. 	            else
  147. 	            {            
  148.  
  149. 	                arr[j]=-1;
  150.  
  151. 	            }
  152. 	         //  cout<<s[j]<<" ";
  153. 	            j++;}
  154. //cout<<"\n";	        j=1;
  155.  
  156.  
  157. 	     int k=-2;
  158.  
  159.  
  160. 	    /* int a[]={-1,1,-1,1,1,1,-1,-1,1,-1,1,-1,-1,-1};
  161. 	     */
  162.  
  163.  
  164.  
  165. 	          int g=largestSub(arr, n, k); 
  166. 	      //  cout<<g;
  167. 	        if(g>f)
  168. 	        {
  169. 	            f=g;
  170. 	        }
  171. 	      //  cout<<"\n";
  172.  
  173.  
  174. 	       c++;i++;}
  175.  
  176.  
  177. 	    cout<<f<<"\n";
  178.  
  179.  
  180. 	}
  181. return 0;
  182. }
Runtime error #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/FLGov6
language:
C++14 (gcc 8.3)
created:
4 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!