leetcode - Maximum Subarray

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

click to show more practice.

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

class Solution {
public:
    int maxSubArray(int A[], int n) {
		int max = A[0],s = A[0];
		for (int i = 1; i < n; i++)
		{
			if(s < 0)
			{
				s = A[i];
			}
			else
			{
				s += A[i];
			}
			if(max < s)
			{
				max = s;
			}
		}
#if 0
		std::cout << max << std::endl;
#endif // 1

		return max;
    }
};