fork download 
  1. #include<iostream>  //Largest sum
  2. #include<vector>
  3. #include<unordered_map>
  4. using namespace std;
  5. int longestSubarray(vector<int>&store,int k){
  6.     unordered_map<int, int> preSum;
  7.     int maxLen = 0;
  8.     int sum = 0;
  9.     for (int i = 0; i < store.size();i++){
  10.         sum = sum + store[i];
  11.  
  12.         // If total sum from index 0 to i is equal to k
  13.         if(sum==k){
  14.             maxLen = max(maxLen, i + 1);
  15.         }
  16.         int rem = sum - k;
  17.         if(preSum.find(rem)!=preSum.end()){
  18.             int newLen=i-preSum[rem];
  19.             maxLen = max(newLen, maxLen);
  20.         }
  21.         if(preSum.find(sum)==preSum.end()){ //This ensures you only store the first occurrence of each prefix sum as we want max length
  22.             preSum[sum] = i;
  23.         }
  24.     }
  25.     return maxLen;
  26. }
  27. int main(){
  28.     vector<int> arr = {2, 0, 0, 3};
  29.     int k = 3;
  30.     int result = longestSubarray(arr, k);
  31.     cout << "The maximum subarray with sum equal to k " << result;
  32.  
  33.     return 0;
  34. }
  35.  
  36.  
  37.  
  38.  
  39.  
  40. // #include<iostream>  //Smallest sum of subarray
  41. // #include<vector>
  42. // #include<unordered_map>
  43. // using namespace std;
  44. // int smallestSubarray(vector<int>&store,int k){
  45. //     unordered_map<int, int> preSum;
  46. //     int minLen = 1e9;
  47. //     int sum = 0;
  48. //     for (int i = 0; i < store.size();i++){
  49. //         sum = sum + store[i];
  50. //         if(sum==k){
  51. //             minLen = min(minLen, i + 1);
  52. //         }
  53. //         int rem = sum - k;
  54. //         if(preSum.find(rem)!=preSum.end()){
  55. //             int newLen=i-preSum[rem];
  56. //             minLen = min(newLen, minLen);
  57. //         }
  58.  
  59. //             preSum[sum] = i;   //for the smallest subarray
  60.  
  61. //     }
  62. //     return minLen;
  63. // }
  64. // int main(){
  65. //     vector<int> arr = {2, 0, 0, 3};
  66. //     int k = 3;
  67. //     int result = smallestSubarray(arr, k);
  68. //     cout << "The minimum subarray with sum equal to k " << result;
  69.  
  70. //     return 0;
  71. // }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin 
Standard input is empty
stdout 
The maximum subarray with sum equal to k 3
https://ideone.com/ABedFH
language:
C++ (gcc 8.3)
created:
2 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!