给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶:
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
思路：从头开始遍历数组，用sum累加数字和，若数字和小于0，记为0；若数字和大于0则加入最终结果中；若所有数字均为负数则选择最大的一个数并返回。
import java.util.Arrays;public class Main {public static void main(String[] args) {int[] nums = { -2, -5, 4, -1, 0 };System.out.println(maxSubArray(nums));}public static int maxSubArray(int[] nums) {int sum = 0;int max = 0;int k = 0;// 计算所有数字中负数个数for (int j = 0; j < nums.length; j++) {sum += nums[j];if (sum > max)max = sum;if (sum < 0) {k++;sum = 0;}}if (k == nums.length) {// 所有数字全为负数Arrays.sort(nums);return nums[k - 1];// 返回最大的负数}return max;}
}