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.