I was asked this in an interview sometime ago. The problem simply stated is “Find the contiguous subsequence in a sequence of numbers which has the largest sum.”. The problem was first presented in 1977, and a linear time solution was reported in 1984. Of course I was asked to solve it in the course of a ~30min interview. 🙂
The linear time solution is called Kadane’s Algorithm, you can read about it on wikipedia. The solution first simplifies the problem, by saying we’re only looking for positive sums. That is, we don’t care about the case where the maximum sum is negative. We can then solve the problem relatively easily but finding the maximum run to each position, if the current maximum subarray value every drops below zero we just discard it (because we’d never want to sum from a negative value, it would be better to sum from zero). Here’s a python implementation of this from wikipedia:
def max_subarray(A):
max_ending_here = max_so_far = 0
for x in A:
max_ending_here = max(0, max_ending_here + x)
max_so_far = max(max_so_far, max_ending_here)
return max_so_far
If we now want to generalize this to the case where the maximum subarray is negative (i.e. everything in the array is negative). We can do that, rather than saying if we go below zero we want to discard the previous parts of the array, we say if the sub goes below the current value as follows:
def max_subarray(A):
max_ending_here = max_so_far = A[0]
for x in A[1:]:
max_ending_here = max(x, max_ending_here + x)
max_so_far = max(max_so_far, max_ending_here)
return max_so_far
Here’s a solution in C++:
#include <iostream>
#include <vector>
#include <stdlib.h>
using namespace std;
int max_subarray(vector<int> &array) {
int max_ending_here = array[0];
int max_so_far = array[0];
for(int n=1;n<array.size();n++) {
if(array[n] < (max_ending_here+array[n])) max_ending_here = max_ending_here+array[n];
else max_ending_here = array[n];
if(max_so_far < max_ending_here) max_so_far = max_ending_here;
}
return max_so_far;
}
int main() {
vector<int> data;
srand(time(NULL));
for(int n=0;n<10;n++) data.push_back((int)(rand()%10)-5);
cout << "data: ";
for(int n=0;n<data.size();n++) cout << data[n] << " ";
cout << endl;
int maxsub = max_subarray(data);
cout << "Max subarray is: " << maxsub << endl;
}
RSS