LeetCode - #53 Maximum Subarray: Passed

30_day_03_maximum_subarray.cpp

#include <vector>
#include <algorithm>

struct SubArray
{
	std::vector<int>::iterator low;
	std::vector<int>::iterator high;
	int sum;
};

class Solution {
public:
	SubArray findMaxCrossingSubArray(std::vector<int> &nums,std::vector<int>::iterator low,std::vector<int>::iterator middle,std::vector<int>::iterator high)
	{
		SubArray result;

		int sum=0;
		float leftSum=-std::numeric_limits<float>::infinity();
		for (std::vector<int>::iterator candidate=middle; candidate >= low; candidate--)
		{
			sum=sum+(*candidate);
			if (sum > leftSum)
			{
				leftSum=sum;
				result.low=candidate;
			}
		}

		sum=0;
		float rightSum=-std::numeric_limits<float>::infinity();
		for (std::vector<int>::iterator candidate=middle+1; candidate <= high; candidate++)
		{
			sum=sum+(*candidate);
			if (sum > rightSum)
			{
				rightSum=sum;
				result.high=candidate;
			}
		}

		result.sum=leftSum+rightSum;
		return result;
	}

	SubArray findMaxSubArray(std::vector<int> &nums,std::vector<int>::iterator low,std::vector<int>::iterator high)
	{ 
		if (low == high) return SubArray({low,high,*low});
		std::vector<int>::iterator middle=low+std::distance(low,high)/2;
		SubArray left=findMaxSubArray(nums,low,middle);
		SubArray right=findMaxSubArray(nums,middle+1,high);
		SubArray crossing=findMaxCrossingSubArray(nums,low,middle,high);
		if (left.sum >= right.sum && left.sum >= crossing.sum) return left;
		if (right.sum >= left.sum && right.sum >= crossing.sum) return right;
		return crossing;
	}

	int maxSubArray(std::vector<int>& nums)
	{	
		return findMaxSubArray(nums,nums.begin(),nums.end()-1).sum;
	}
};