#include <iostream>
#include "bits/stdc++.h"

using namespace std;

int main()
{
    int arr[4] = {3, 5, 7, 4};

    // Prefix
    vector<int>pre(5); // 4+1 (1-Based)
    for(int i=1; i<5; i++)
    {
        pre[i] = pre[i-1] + arr[i-1]; // all values before this index + value of current index
    }

    // Suffix
    vector<int>suff(6); // 4 + 2 (1-Based)
    for(int i=4; i>=1; i--)
    {
        suff[i] = suff[i+1] + arr[i-1]; // all values after this index + value of current index
    }

    // Frequency range (count)
    // Count 'a' from range l to r
    string a = "abccabaac";
    vector<int>freq(a.size()+1); // (1-Based)
    for(int i=1; i<=a.size(); i++)
    {
        if(a[i-1]=='a')
        {
            freq[i]=1;
        }
    }
    // {1,0,0,0,1,0,1,1,0}
    for(int i=1; i<=a.size(); i++)
    {
        freq[i]+=freq[i-1];
    }
    // {1,1,1,1,2,2,3,4,4}
    int rl=3,rr=6;
    // freq[rr]-freq[rl-1]

    // Range
    // 1 3
    // 2 3
    // 1 4
    // Add the value to left and subtract from right + 1
    vector<int>range(6); // Size = max right + 1
    // 1 3
    range[1]++;
    range[4]--;
    // 2 3
    range[2]++;
    range[4]--;
    // 1 4
    range[1]++;
    range[5]--;
    for(int i=1; i<6; i++)
    {
        range[i]+=range[i-1];
    }
    // range = {2,3,3,1}

    // Sliding Window
    // Q1: Find max sum of subarray
    int arr1[6] = {-1,2,3,1,-3,2};
    int sum=0,maxi=0;
    for(int i=0; i<6; i++)
    {
        sum+=arr1[i];
        if(sum < 0)
        {
            sum = 0; // No need for negative values
        }
        maxi=max(maxi,sum);
    }
    // maxi = 6

    //Q2: Find count of subarrays with sum = k
    int arr2[9] = {2,-1,3,5,-6,2,4};
    int k=2;
    int summ=0;
    map<int,int>mp;
    mp[0]++;
    int s=0,cntt=0;
    for(int i=0; i<9; i++)
    {
        summ+=arr2[i];
        cntt+=mp[summ-k];
        mp[summ]++;
    }
    // cntt = 4

    //Q3: Find max length of string with maximum number of 0's = k
    string ss = "010100011";
    int kk=3;
    int left=0,right=0;
    int cntsofar=0;
    int maxii=0;
    while(left<ss.size() && right<ss.size())
    {
        if(cntsofar <= kk)
        {
            maxii=max(maxii,right-left+1);
            if(ss[right]=='0')
            {
                cntsofar++;
            }
            right++;
        }
        else
        {
            if(ss[left]=='0')
            {
                cntsofar--;
            }
            left++;
        }
    }
    // maxii = 6
}