解法一：O（n^2)
public int maxSubArray(int[] nums) { int max = nums[0]; for(int i = 0; i < nums.length; i++){ int sum = 0; for(int j = i; j < nums.length; j++){ sum += nums[j]; if(sum > max){ max = sum; } } } return max; }解法二：O(n)
public int maxSubArray(int[] nums) { int max = nums[0]; int sum = 0; for(int num : nums){ if(sum < 0){ sum = 0; } sum += num; max = Math.max(sum, max); } return max; }聲明兩個變量，最大和max，當前和sum。如果sum<0，加上之前的sum必定比不加要小，所以拋棄之前的子串，重置sum為0。反之，如果sum>0，則會給後面的max做貢獻，所以要加入計算。一路遍歷過來凡是保留到sum中的子串，必定大於0。
解法三：O(n)
public int maxSubArray(int[] nums) { int maxEndHere = nums[0]; int max = nums[0]; for(int i = 1; i < nums.length; i++){ maxEndHere = Math.max(maxEndHere + nums[i], nums[i]); max = Math.max(max, maxEndHere); } return max; }