# DS JOURNEY

I started exploring dsa quite recently, the process went like this,
- first solving leetcode daily challenges,
- then learning dsa through js,
- later, solving easy questions in leetcode in cpp

But, overall it looked quite staggered, with me not having an end target and being productive one day and worried the other day.

The following readme is supposed to be the script/ planner for my videos that I wanted to record while going through dsa, this is needed because,

Back in high school and colleges, we had the concept of revision where in we are supposed to write the same question or poem 10 times, in 10 different exams...

Similarly for JEE, the core of learning was to solve good number of questions from a concept, so that that concept fits into the mind.

### KADANES ALGORITHM:

I would like to name this as my hello-world problem for DSA, after I have stumbled over many problems in the striver's DSA sheet.

#### Q1:
Find the maximum sum in subarray for a given array, leetcode-53.

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.


While solving any dsa question, first take a pen and paper...arrive at a naive approach, calculate the time complexity, then try to implement the naive approach if its good enough to start with, then try to use optimised data structures or algorithmic techniques to arrive at a better solution.

### Brute Force Approach:
Here the naive approach is to calculate sum of every possible subarray and find the maximum among them.

*Brute Force Approach: Iteration 0 (left) and Iteration 1 (right)*

But to achieve the same, we need to traverse the array many times, O(n^2) in particular...

this becomes very inefficient as the array size grows..

So, we need to come up with more effective idea for solving this.

### KADANE'S ALGO:

Backward Brute Force Approach: Iteration 0 (left) and Iteration 1 (right)

In this approach lets focus on two elements, A[4] and A[5]... the idea is to observe how we can calculate A[5] using A[4]


From the above figure, we can see that local maxmimum at A[4] is 3 for the elements, [4, -1].

Similarly, it's intitutive that the local maxima at A[5] would be either localmaxima(A[4])+A[5] or A[5], which ever is maximum, so we have..

**local_maximum[i] = max(A[i],(A[i] + local_maximum[i-1])).**

let's code the algorithm now..

#include<iostream>
using namespace std;
int main(){

    int maxSubArray(vector <int>&A){
        int n = A.size();
        int localMax = 0;
        int globalMax = INT_MIN;
        for(int i=0;i<n;i++){
        localMax=max(A[i], A[i]+localMax);
        if(localMax>globalMax) globalMax = localMax;
        }
        return globalMax;
    }
}

Q2:Merge Overlapping Intervals - LC:56

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

ideas: