LeetCode Q53: Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

	class Solution {
	public:
	int maxSubArray(vector<int>& nums) {
	int maxSum=-INT_MAX;
	int curSum=0;
	int p=0;
	while(p<=nums.size()-1){
	curSum=curSum+nums[p];
	curSum=curSum<0? nums[p]:curSum;
	maxSum=curSum>maxSum? curSum:maxSum;
	curSum=curSum>0? curSum:0;
	p++;
	}
	return maxSum;
	}
	};

view raw Q53MaximumSubarray.cpp hosted with ❤ by GitHub

A neater solution:

	class Solution {
	public:
	int maxSubArray(vector<int>& nums) {
	int maxSum = INT_MIN, currentSum = 0;
	for( int i = 0; i < nums.size(); ++i ){
	maxSum = max( maxSum, currentSum+= nums[i] );
	currentSum = ( currentSum < 0 ) ? 0 : currentSum;
	}
	return maxSum;
	}
	};

view raw Q53-2.cpp hosted with ❤ by GitHub

Round 2 solution:
This solution will take into account a case where all numbers are negative.

	class Solution {
	public:
	int maxSubArray(vector<int>& nums) {
	if(nums.empty())
	return 0;
	int maxSum=nums[0];
	int curSum=0;
	for(int i=0; i<nums.size(); i++){
	curSum = curSum + nums[i];
	maxSum = max(curSum, maxSum);
	curSum = curSum<0? 0:curSum;
	}
	return maxSum;
	}
	};

view raw Q53.cpp hosted with ❤ by GitHub