## 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

*calculates the prefix sum for us.*

**curr_sum**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 :