咕泡Java高新offer冲刺班
最大子数组和
public static void main(String[] args) {
System.out.println(new MaxSubarraySum().maxSubArray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}));
}
public int maxSubArray(int[] nums) {
return maxSubArray(nums, 0, nums.length - 1);
}
public int maxSubArray(int[] nums, int start, int end) {
if (start == end) {
return nums[end];
}
if (start > end) {
return 0;
}
if (start + 1 == end) {
return Math.max(Math.max(nums[start], nums[end]), nums[start] + nums[end]);
}
int mid = (start + end) / 2;
int leftMax = maxSubArray(nums, start, mid - 1);
int rightMax = maxSubArray(nums, mid + 1, end);
int midMax = getMidMax(nums, start, end, mid);
return Math.max(Math.max(leftMax, rightMax), midMax);
}
