53-Maximum-Subarray.md

53. Maximum Subarray (Java)

Problem

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.

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.

Solution 1.

Kadane's演算法能夠使用一個迴圈得出答案，若要更快速就要使用分而治之來實作了，間單來說Kadane's演算法就是當遇到負數就歸零，每次相加結果取最大數。

• 陣列走訪
• Run Time: 14 ms
• 時間複雜度: O(n)
• 空間複雜度: O(1)

class Solution {
    public int maxSubArray(int[] nums) {
		int tot = 0, max = Integer.MIN_VALUE;
		for (int i = 0; i < nums.length; i++) {
			tot += nums[i];
			if (max < tot) {
				max = tot;
			}
			if (tot <= 0) {
				tot = 0;
			}
		}
		return max;
    }
}