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. 	//subarray with sum==k
  49. 	unordered_map<int,int> ok;
  50. 	int sum=0,count=0;
  51. 	int k=-10;
  52. 	vector<int> arr={10,-2,2,-20 ,10}; //   10 8 10 -10 0
  53. 	ok[0]=1;
  54. 	for(int i=0;i<arr.size();i++){
  55. 		sum+=arr[i];
  56. 		if(ok.find(sum-k)!=ok.end()){
  57. 			count+=ok[sum-k];
  58. 		}
  59. 		ok[sum]++;
  60. 	}
  61. 	cout<<count;
  62.  
  63.  
  64.  
  65.  
  66.  
  67.  
  68.  
  69.  
  70.  
  71.  
  72.  
  73.  
  74.  
  75.  
  76.  
  77.  
  78.  
  79.  
  80.  
  81.  
  82.  
  83.  
  84.  
  85. 	return 0;
  86. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3
https://ideone.com/b7YAZI
longest common sequence
language:
C++14 (gcc 8.3)
created:
15 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!