## A Brief Introduction

Problem Statement – Find the maximum sum sub-array of the given array

Let us assume the maximum sum sub-array lies between index L to R. We can actually look at it as prefix sum [1,R] – prefix sum [1,L-1]. To maximize this difference, we need to maximize the ps[1,R] and minimize the ps[1,L-1].

Another trivial but important condition while performing above algo is L <= R. So, let us assume that we are scanning the array and at each ith position, we assume the ps[1,R] is nothing but ps[1,i], it means assume ith position as the best position to get the maximum subarray sum.

We, now need to subtract the minimum possible ps[1, L] from it. Let us say, the variable min_sum stores the minimum possible sum seen so far.

The variable best will store the best possible answer for us. The variable curr_sum calculates the prefix sum for us.

The leetcode problem is exactly this, you can try your hands on the algorithm here – https://leetcode.com/problems/maximum-subarray/

```class Solution {
public:
int maxSubArray(vector<int> nums) {

int best = INT_MIN;
int min_sum= 0;
int curr_sum = 0;
for(int i=0;i<nums.size();i++){
curr_sum += nums[i];
best = max(best,curr_sum - min_sum);
min_sum = min(min_sum, curr_sum);
}
return best;
}
};
```

We will see more variations of this algorithm in later sections. Some problems we will be dealing in this section are :