day96（2.25）——leetcode面试经典150

53. 最大子数组和

53. 最大子数组和

题目：

题解：

class Solution { public int maxSubArray(int[] nums) { //当前选自己 or 接着加，全局取最大 //贪心+一维动态规划 //当前最优解，全局最优解 int currentRes = nums[0]; int maxRes = nums[0]; for(int i=1;i<nums.length;i++) { currentRes = Math.max(currentRes+nums[i], nums[i]); maxRes = Math.max(currentRes, maxRes); } return maxRes; } }

918. 环形子数组的最大和

918. 环形子数组的最大和

题目：

题解：

class Solution { public int maxSubarraySumCircular(int[] nums) { int minCurRes = nums[0], maxCurRes = nums[0]; int minRes = nums[0], maxRes = nums[0]; int total = nums[0]; for(int i=1;i<nums.length;i++) { minCurRes = Math.min(minCurRes+nums[i], nums[i]); minRes = Math.min(minRes, minCurRes); maxCurRes = Math.max(maxCurRes+nums[i], nums[i]); maxRes = Math.max(maxRes, maxCurRes); total+=nums[i]; } //说明全是负数 if(maxRes < 0) { return maxRes; } return Math.max(maxRes, total-minRes); } }