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.

- Initialize two variables
**current_max**and**global_max**with the first element in the array. - 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) - 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[0]; int globalMax = nums[0]; 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.**

## 2 comments

Comments are closed.