fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. pair<int,int>getMaxMin(const vector<int>&arr,int n,int k){
  4. 	unordered_map<int,int>max;
  5. 	unordered_map<int,int>min;
  6. 	max[0]=0;
  7. 	int sum=0;
  8. 	int maxi=0;
  9. 	int mini=1e9;
  10. 	for(int i=1;i<=n;i++){
  11. 		sum+=arr[i-1];
  12. 		int x=sum-k;
  13. 		if(max.find(x)!=max.end()){
  14. 			int dist=max[x]+1;
  15. 			int maxD=i-dist+1;
  16. 			if(maxD>maxi){
  17. 				maxi=maxD;
  18. 			}
  19. 		}
  20. 		if(max.find(x)!=max.end()){
  21. 			int dist=max[x]+1;
  22. 			int minD=i-dist+1;
  23. 			if(minD<mini){
  24. 				mini=minD;
  25. 			}
  26. 		}
  27. 		if(max.find(x)==max.end()){
  28. 			max[sum]=i;
  29. 		}
  30. 		min[sum]=i;
  31. 	}
  32. 	return {maxi,mini};
  33.  
  34. }
  35. int getMmcount(const vector<int>&arr,int n,int k,int getCount){
  36. 	int count=0;
  37. 	int sum=0;
  38. 	if(getCount==0){
  39. 		return 0;
  40. 	}
  41. 	for(int i=0;i<getCount;i++){
  42. 		sum+=arr[i];
  43. 	}
  44. 	if(sum==k){
  45. 		count++;
  46. 	}
  47. 	for(int i=getCount;i<n;i++){
  48. 		sum+=arr[i]-arr[i-getCount];
  49. 		if(sum==k){
  50. 			count++;
  51. 		}
  52. 	}
  53. 	return count;
  54.  
  55.  
  56. }
  57.  
  58. int main() {
  59. 	// your code goes here
  60. 	vector<int>arr={1,2,3,4,5,-1,6};
  61. 	int k=9;
  62. 	int n=arr.size();
  63. 	auto[maxL,minL]=getMaxMin(arr,n,k);
  64. 	int MCount=getMmcount(arr,n,k,maxL);
  65. 	int mCount=getMmcount(arr,n,k,minL);
  66.  
  67. 	cout<<"The maximum length is: "<<maxL<<" and its count:"<<MCount<<endl;
  68. 	cout<<"The minimum length is: "<<minL<<" and its count:"<<mCount<<endl;
  69.  
  70.  
  71. 	return 0;
  72. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
The maximum length is: 3 and its count:1
The minimum length is: 2 and its count:1
https://ideone.com/n2RuSz
language:
C++ (gcc 8.3)
created:
5 days ago
visibility:
public

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!