fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5. 	// longest common sequence
  6. 	// vector<int> arr={0,3,7,2,5,8,4,6,0,1};
  7. 	// unordered_map<int,bool> ok, check;
  8. 	// for(int i=0;i<arr.size();i++){
  9. 	// 	ok[arr[i]]=true;
  10. 	// }
  11. 	// int k=0;
  12. 	// for(int i=0;i<arr.size();i++){
  13. 	// 	if(ok.find(arr[i]-1)==ok.end() && ok[arr[i]]==true){
  14. 	// 	int t=arr[i];
  15. 	// 	int count=0;
  16. 	// 	while(ok[t]){
  17. 	// 			count++;
  18. 	// 			ok[t]=false;
  19. 	// 			t=t+1;
  20. 	// 	}
  21.  
  22. 	// 	k=max(count,k);
  23. 	// 	}
  24. 	// }
  25. 	// cout<<k;
  26.  
  27.  
  28. 	//longest subarry with sum=0
  29. 	/* we will first calculate the prefix sum and find the max distance between the same element
  30. 	*/
  31. 	vector<int> arr={1,0,3};
  32. 	unordered_map<int,int> ok;
  33. 	int n=arr.size();
  34. 	vector<int> pre(n+1,0);
  35. 	for(int i=1;i<=n;i++){
  36. 		pre[i]=pre[i-1]+arr[i-1];
  37. 	}
  38. 	int count=0;
  39. 	for(int i=1;i<=n;i++){
  40. 		if(ok.find(pre[i])==ok.end()){
  41. 			ok[pre[i]]=i;
  42. 		}else{
  43. 			count=max(count,i-ok[pre[i]]);
  44. 		}
  45. 	}
  46. 	cout<<count;
  47.  
  48.  
  49.  
  50.  
  51.  
  52.  
  53.  
  54.  
  55.  
  56.  
  57.  
  58.  
  59.  
  60.  
  61.  
  62.  
  63.  
  64.  
  65.  
  66.  
  67.  
  68.  
  69.  
  70. 	return 0;
  71. }
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/b7YAZI
longest common sequence
language:
C++14 (gcc 8.3)
created:
8 hours 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!