Kadane-Algorithm.cpp

// 1. 🔥 Kadane’s Algorithm (Max Subarray Sum)

// 👉 Use when: Find maximum sum of a continuous subarray

// Formula:

// current_sum = max(arr[i], current_sum + arr[i])
// max_sum = max(max_sum, current_sum)


#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int>arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    int current_sum=0;
    int max_sum=INT_MIN;
    for(int i=0;i<n;i++){
        current_sum=max(arr[i], current_sum + arr[i]);
        max_sum=max(max_sum, current_sum);
    }
    cout<<max_sum<<endl;

    return 0;
}


// 📊 Prefix Sum — Full Explanation
// 👉 What is Prefix Sum?
// It’s a way to precompute cumulative sums so that you can answer range queries in O(1) time.


// 📌 Formula

// P[i] = P[i-1] + a[i]
// 🔍 Range Sum Formula

// Range_Sum(L, R) = P[R] - P[L-1]

// To find sum from L to R:
//P[R] gives sum from 0 to R
//P[L-1] gives sum from 0 to L-1
//P[L-1] remove unwanted part from sum of 0 to R
//Subtracting gives sum from L to R




#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int>arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    //build prefix sum array
    vector<int>P(n);
    P[0]=arr[0];
    for(int i=1;i<n;i++){
       P[i]=P[i-1]+arr[i];
    }
    int q;
    cin>>q;
    while(q--){
        int L,R;
        cin>>L>>R;
        int range_sum;
        if(L==0){
            range_sum=P[R];
        } else {
            range_sum=P[R]-P[L-1];
        }
        cout<<range_sum<<endl;
    }
     // Print prefix array
     for(int i=0;i<n;i++){
        cout<<P[i]<<" ";
     }
    cout<<endl;
    return 0;
}


// 🪟 Sliding Window — Full Explanation
// 👉 When to Use

// Subarrays (continuous)
// Condition-based problems
// Especially when elements are non-negative

// 🧠 Mathematical Concept
// We maintain a window:

// 👉 Goal:

// Expand  R (increase sum)
// If condition breaks → move  L (reduce sum)

// 🔑 Key Property (Why it works)
// If all elements ≥ 0:

// If sum increases when R↑
// It will never decrease by adding more elements (R↑)

// 👉 Then:

// Increasing  R → sum increases
// Increasing  L → sum decreases
// This monotonic behavior makes it O(N)
// 🧪 Example (Important)
// 📊 Problem:
// Find longest subarray with sum ≤ K


#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    vector<int> arr(n);
    // ✅ Take input once
    for(int i = 0; i < n; i++){
        cin >> arr[i];
    }
    int k;
    cin >> k;
    int left = 0, sum = 0, max_len = 0;
    for(int right = 0; right < n; right++){
        sum += arr[right];   // ✅ use existing array
        // shrink window if invalid
        while(sum > k){
            sum -= arr[left];
            left++;
        }
        // update maximum length
        max_len = max(max_len, right - left + 1);
    }
    cout << "Maximum length of subarray with sum <= " << k << " is: " << max_len << endl;
    return 0;
}



// 👉 Two Pointer Technique
// 🧠 When to Use

// Array is sorted
// Find pair / triplet / condition-based problems
// Reduce O(N²) → O(N)

// 🧠 Mathematical Idea
// We are checking:
//aL + aR = target

// 👉 Because array is sorted:
// If sum is too small → increase it
// If sum is too large → decrease it
// 🔑 Why It Works (Important)

// Since:
//a0 ≤ a1 ≤ a2 ≤ ... ≤ an-1

// 👉 Then:
// Moving left → right increases value
// Moving right → left decreases value



#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int>arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    int target;
    cin>>target;
    int left=0, right=n-1;
    bool found=false;
    while(left<right){
        int sum=arr[left]+ arr[right];
        if(sum==target){
            cout<<"Pair found: "<<arr[left]<<" and "<<arr[right]<<endl;
            found=true;
            break;
        } else if(sum < target){
            left++;
        } else {
            right--;
        }
    }
    if(!found){
        cout<<"No pair found with the given sum."<<endl;
    }
    return 0;
}




// arr = [1, 2, 3, 4, 6]
// target = 6
// left = 0, right = 4 → sum = 1 + 6 = 7 > target → right--
// left = 0, right = 3 → sum = 1 + 4 = 5 < target → left++
// left = 1, right = 3 → sum = 2 + 4 = 6 == target → pair found (2, 4)




// 🗂️ HashMap Technique (Subarray Sum = K)
// 👉 Problem

// Find number of subarrays whose sum = K

// 🧠 Mathematical Idea

// We know:
//prefix[i] = a0 + a1 + ... + ai
// To find subarray sum from L to R:
//subarray_sum(L, R) = prefix[R] - prefix[L-1]
// 👉 Then:
// prefix[R] - prefix[L-1] = K
// prefix[L-1] = prefix[R] - K





#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int>arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    int k;
    cin>>k;
    unordered_map<int, int>mp;
    int prefix_sum=0;
    int count=0;
    mp[0]=1; // Base case: prefix sum of 0 occurs once
    for(int i=0;i<n;i++){
        prefix_sum+=arr[i];
        int required_sum=prefix_sum-k;
        if(mp.find(required_sum)!=mp.end()){
            count+=mp[required_sum]; // Add occurrences of required_sum
        }
        mp[prefix_sum]++; // Increment count of current prefix sum
    }
    cout << "Number of subarrays with sum equal to " << k << " is: " << count << endl;

}





// ⚡ Contribution Technique
// 👉 When to Use

// When problem asks for:
// Sum of all subarrays
// Total contribution of elements
// Instead of generating all subarrays (O(N²)), we use math → O(N)
// 🧠 Core Idea

// 👉 Instead of:
// Generating all subarrays
// 👉 Think:
// How many times each element appears in all subarrays?

// 📊 Mathematical Intuition
// For an element at index i in an array of size n:

// 🔹 Left choices:
// You can start subarray from: 0, 1, 2, ..., i
// Total left choices = i + 1

// 🔹 Right choices:
// You can end subarray at: i, i+1, i+2, ..., n-1
// Total right choices = n - i

// 🔹 Total subarrays containing element at index i:
// (i + 1) * (n - i)
//total contribution of element at index i = arr[i] * (i + 1) * (n - i)



#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int>arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    long long total_sum=0;
    for(int i=0;i<n;i++){
        long long count=(long long)(i+1)*(n-i);
        total_sum+=arr[i]*count;
    }
    cout << "Total sum of all subarrays is: " << total_sum << endl;
}





//print all subarrays of an array


#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int>arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    // Generate all subarrays
    for(int i=0;i<n;i++){
        for(int j=i;j<n;j++){
            for(int k=i;k<=j;k++){
                cout<<arr[k]<<" ";
            }
            cout<<endl;
        }
    }
    return 0;
}