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[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.