剑指42 连续子数组的最大和

解法一 动态规划

  1. class Solution {
  2.     public int maxSubArray(int[] nums) {
  3.         if (nums == null || nums.length == 0)
  4.             return 0;
  6.         int pre  = 0;
  7.         int ans = nums[0];
  8.         for (int num : nums) {
  9.             pre = Math.max(pre + num, num);
  10.             ans = Math.max(pre, ans);
  11.         }
  12.         return ans;
  13.     }
  14. }

解法二 分治法

  1. class Solution {
  2.     public int maxSubArray(int[] nums) {
  3.         if (nums == null || nums.length == 0)
  4.             return 0;
  6.         return maxSubSum(nums, 0, nums.length - 1);
  7.     }
  9.     private int maxSubSum(int[] nums, int left, int right) {
  10.         int ans = 0;
  11.         if (left == right)
  12.             return nums[left];
  14.         int mid = (left + right) / 2;
  15.         int maxLeftSum = maxSubSum(nums, left, mid);
  16.         int maxRightSum = maxSubSum(nums, mid + 1, right);
  18.         int maxLeftBorderSum = nums[mid];
  19.         int leftBorderSum = 0;
  20.         int maxRightBorderSum = nums[mid];
  21.         int rightBorderSum = 0;
  23.         for (int i = mid; i >= left; i--) {
  24.             leftBorderSum += nums[i];
  25.             maxLeftBorderSum = Math.max(leftBorderSum, maxLeftBorderSum);
  26.         }
  28.         for (int j = mid; j <= right; j++) {
  29.             rightBorderSum += nums[j];
  30.             maxRightBorderSum = Math.max(rightBorderSum, maxRightBorderSum); 
  31.         }
  33.         int maxMidSum = maxLeftBorderSum + maxRightBorderSum - nums[mid];
  35.         ans = getMaxOfThree(maxLeftSum, maxMidSum, maxRightSum);
  37.         return ans;
  38.     }
  40.     private int getMaxOfThree(int a, int b, int c) {
  41.         int ans;
  42.         if (a > b)
  43.             ans = a;
  44.         else 
  45.             ans = b;
  47.         if (ans < c)
  48.             return c;
  50.         return ans;
  51.     }
  52. }