咕泡Java高新offer沖刺班
最大子數(shù)組和
?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);
? ?}
