# Maximum Sum SubArray – Kadane’s Algorithm (DP-01)

Given an array which can contain both positive and negative integers, find the length of the subarray which has the maximum sum.

Sample Input: [ -2, 1, -3, 4, -1, 2, 1, -5, 4 ]
Expected Output: 6
Explanation: The subarray [4, -1, 2, 1] has the maximum sum which is 6.

Algorithm:

The problem can be solved using dynamic programming in linear time. The name of the algorithm used here is Kadane’s algorithm.

1. Initialize two variables current_max and global_max with the first element in the array.
2. Loop starting from second element of the array till the last element. In each iteration, do the following:
Set current_max = maximum (arr[i], arr[i] + current_sum)
Set global_max = maximum (current_max, global_max)
3. This works because for every element, we have two choices – Either we can include the current element in our current max or we can start the current max over again with the current element.
```/* Author => Raunak Jain */

#include <bits/stdc++.h>
using namespace std;

int helper(vector<int> nums){
int currMax = nums;
int globalMax = nums;
for(int i=1; i<nums.size(); i++){
currMax = max(nums[i], nums[i]+currMax);
globalMax = max(currMax, globalMax);
}
return globalMax;
}

int main(){
vector<int> nums = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
cout<<helper(nums);
return 0;
}```

Also take a look at another popular interview question Rod cutting problem.