53. Maximum Subarray 发表于 2022-01-08 DP1234567891011121314151617181920class Solution { public int maxSubArray(int[] nums) { // 定义 dp[i] 为以 nums[i] 结尾的子数组的最大和 int[] dp = new int[nums.length]; dp[0] = nums[0]; int maxSum = dp[0]; for (int i = 1; i < nums.length; i++) { if (dp[i - 1] > 0) { dp[i] = dp[i - 1] + nums[i]; } else { dp[i] = nums[i]; } maxSum = Math.max(maxSum, dp[i]); } return maxSum; }} Divide and Conquer123456789101112131415161718192021222324252627282930313233343536class Solution { public int maxSubArray(int[] nums) { return maxSubArray(nums, 0, nums.length - 1); } private int maxSubArray(int[] nums, int left, int right) { if (left == right) { // 不能再拆分,直接返回 return nums[left]; } // 此时 left 一定小于 right int mid = (left + right) >>> 1; return max(maxSubArray(nums, left, mid), maxSubArray(nums, mid + 1, right), maxSum(nums, left, mid, right)); } private int max(int a, int b, int c) { return Math.max(a, Math.max(b, c)); } private int maxSum(int[] nums, int left, int mid, int right) { int sum = 0, leftMaxSum = Integer.MIN_VALUE, rightMaxSum = Integer.MIN_VALUE; for (int i = mid; i >= left; i--) { sum += nums[i]; leftMaxSum = Math.max(leftMaxSum, sum); } sum = 0; for (int i = mid + 1; i <= right; i++) { sum += nums[i]; rightMaxSum = Math.max(rightMaxSum, sum); } return leftMaxSum + rightMaxSum; }} Reference53. Maximum Subarray剑指 Offer 42. 连续子数组的最大和