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.  
  107. int main()
  108. {
  109. 	int t;
  110. 	cin>>t;
  111. 	while(t--)
  112. 	{   
  113. 	    int f=-1;
  114. 	    int n;cin>>n;
  115. 	    string s;
  116. 	    cin>>s;
  117. 	     char c='a';
  118. 	    int i=0;
  119. 	    while(i<26)
  120. 	    {
  121. 	      int arr[n];
  122.  
  123. 	       int j=0;
  124. 	        while(j<n)
  125. 	        {
  126. 	            if(s[j]==c)
  127. 	            {
  128. 	                arr[j]=1;
  129. 	            }
  130. 	            else
  131. 	            {            
  132.  
  133. 	                arr[j]=-1;
  134.  
  135. 	            }
  136. 	         //  cout<<s[j]<<" ";
  137. 	            j++;}
  138. //cout<<"\n";	        j=1;
  139.  
  140.  
  141. 	     int k=-2;
  142.  
  143.  
  144. 	    /* int a[]={-1,1,-1,1,1,1,-1,-1,1,-1,1,-1,-1,-1};
  145. 	     */
  146.  
  147.  
  148.  
  149. 	          int g=largestSub(arr, n, k); 
  150. 	      //  cout<<g;
  151. 	        if(g>f)
  152. 	        {
  153. 	            f=g;
  154. 	        }
  155. 	      //  cout<<"\n";
  156.  
  157.  
  158. 	       c++;i++;}
  159.  
  160.  
  161. 	    cout<<f<<"\n";
  162.  
  163.  
  164. 	}
  165. return 0;
  166. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
4
3
abc
4
aaaa
10
aabcdefghh
1
a
stdout
copy 
3
4
5
1
https://ideone.com/wvpXju
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!