DSA Pages

This can be done easily by maintaining an accumalator variable and looping through the whole array.

int getSum(int arr[],int n){
    int sum = 0;
    for(int i=0; i<n; i++)
        sum+=arr[i];
    return sum;
}

This can be done easily by maintaining a maxi variable with initial value such that this can't never be a maximum and looping throught the whole array.

int getMax(int arr[],int n){
    int maxi = INT_MIN;
    for(int i=0; i<n; i++)
        maxi = max(maxi,arr[i]);
    return maxi;
}

This can be done easily by maintaining a mini variable with initial value such that this can't never be a minimum and looping throught the whole array.

int getMin(int arr[],int n){
    int mini = INT_MAX;
    for(int i=0; i<n; i++)
        mini = min(mini,arr[i]);
    return mini;
}

Problem link

The idea is to have the sum of subarray which is under current observation and as soon as the current sum become negative we reset it to zero because we don't want it to contribute to our ans. And at each step we update the maxi(The max sum possible)

int maxSubArray(const vector &A) {
    int curr = 0;
    int maxi = 0;
    for(int i=0; i<A.size(); i++){
        curr+=A[i];
        if(curr<0) curr = 0;
        maxi = max(maxi,curr);
    }
    if(maxi==0) return *max_element(A.begin(),A.end());
    return maxi;
}

The complexity of above algorithm is O(N)

We can think that either the subarray will be right half,left half, or middle so we try out all possibilities and get the optimal one.

pair LAS_cross(int arr[], int l, int r)
{
    int mid = (l + r) / 2;
    int leftIndex = mid;
    int rightIndex = mid;
    for (int i = mid; i > l; i--)
    {
        if (arr[i] >= arr[i - 1])
        {
            leftIndex = i - 1;
        }
        else
            break;
    }
    for (int i = mid + 1; i < r; i++)
    {
        if (arr[i] <= arr[i + 1])
        {
            rightIndex = i + 1;
        }
        else
            break;
    }
    return {leftIndex, rightIndex};
}
pair< int, int > LAS(int arr[], int l, int r)
{
    if (l < r)
    {
        int mid = (l + r) / 2;
        pair<int, int> ans_cross = LAS_cross(arr, l, r);
        pair<int, int> ans_left = LAS(arr, l, mid);
        pair<int, int> ans_right = LAS(arr, mid + 1, r);
        int crossDiff = ans_cross.second - ans_cross.first;
        int leftDiff = ans_left.second - ans_left.first;
        int rightDiff = ans_right.second - ans_right.first;
        if (leftDiff > rightDiff && leftDiff > crossDiff)
            return ans_left;
        else if (crossDiff > leftDiff && crossDiff > rightDiff)
            return ans_cross;
        else
            return ans_right;
    } 
    return {l,r};
}

This is a recursive solution and have a time complexity having recurrence realtion as T(N) = 2T(N/2) + O(N) and using Masters'theorem we get the T(N) as T(N) = O(NlogN)