fork download
copy 
  1. #include <iostream>
  2. #include "bits/stdc++.h"
  3.  
  4. using namespace std;
  5.  
  6. int main()
  7. {
  8.     int arr[4] = {3, 5, 7, 4};
  9.  
  10.     // Prefix
  11.     vector<int>pre(5); // 4+1 (1-Based)
  12.     for(int i=1; i<5; i++)
  13.     {
  14.         pre[i] = pre[i-1] + arr[i-1]; // all values before this index + value of current index
  15.     }
  16.  
  17.     // Suffix
  18.     vector<int>suff(6); // 4 + 2 (1-Based)
  19.     for(int i=4; i>=1; i--)
  20.     {
  21.         suff[i] = suff[i+1] + arr[i-1]; // all values after this index + value of current index
  22.     }
  23.  
  24.     // Frequency range (count)
  25.     // Count 'a' from range l to r
  26.     string a = "abccabaac";
  27.     vector<int>freq(a.size()+1); // (1-Based)
  28.     for(int i=1; i<=a.size(); i++)
  29.     {
  30.         if(a[i-1]=='a')
  31.         {
  32.             freq[i]=1;
  33.         }
  34.     }
  35.     // {1,0,0,0,1,0,1,1,0}
  36.     for(int i=1; i<=a.size(); i++)
  37.     {
  38.         freq[i]+=freq[i-1];
  39.     }
  40.     // {1,1,1,1,2,2,3,4,4}
  41.     int rl=3,rr=6;
  42.     // freq[rr]-freq[rl-1]
  43.  
  44.     // Range
  45.     // 1 3
  46.     // 2 3
  47.     // 1 4
  48.     // Add the value to left and subtract from right + 1
  49.     vector<int>range(6); // Size = max right + 1
  50.     // 1 3
  51.     range[1]++;
  52.     range[4]--;
  53.     // 2 3
  54.     range[2]++;
  55.     range[4]--;
  56.     // 1 4
  57.     range[1]++;
  58.     range[5]--;
  59.     for(int i=1; i<6; i++)
  60.     {
  61.         range[i]+=range[i-1];
  62.     }
  63.     // range = {2,3,3,1}
  64.  
  65.     // Sliding Window
  66.     // Q1: Find max sum of subarray
  67.     int arr1[6] = {-1,2,3,1,-3,2};
  68.     int sum=0,maxi=0;
  69.     for(int i=0; i<6; i++)
  70.     {
  71.         sum+=arr1[i];
  72.         if(sum < 0)
  73.         {
  74.             sum = 0; // No need for negative values
  75.         }
  76.         maxi=max(maxi,sum);
  77.     }
  78.     // maxi = 6
  79.  
  80.     //Q2: Find count of subarrays with sum = k
  81.     int arr2[9] = {2,-1,3,5,-6,2,4};
  82.     int k=2;
  83.     int summ=0;
  84.     map<int,int>mp;
  85.     mp[0]++;
  86.     int s=0,cntt=0;
  87.     for(int i=0; i<9; i++)
  88.     {
  89.         summ+=arr2[i];
  90.         cntt+=mp[summ-k];
  91.         mp[summ]++;
  92.     }
  93.     // cntt = 4
  94.  
  95.     //Q3: Find max length of string with maximum number of 0's = k
  96.     string ss = "010100011";
  97.     int kk=3;
  98.     int left=0,right=0;
  99.     int cntsofar=0;
  100.     int maxii=0;
  101.     while(left<ss.size() && right<ss.size())
  102.     {
  103.         if(cntsofar <= kk)
  104.         {
  105.             maxii=max(maxii,right-left+1);
  106.             if(ss[right]=='0')
  107.             {
  108.                 cntsofar++;
  109.             }
  110.             right++;
  111.         }
  112.         else
  113.         {
  114.             if(ss[left]=='0')
  115.             {
  116.                 cntsofar--;
  117.             }
  118.             left++;
  119.         }
  120.     }
  121.     // maxii = 6
  122. }
  123.  
Success #stdin #stdout 0.01s 5472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/qg63xd
language:
C++ (gcc 8.3)
created:
2 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!