Day 80

题目描述

思路

初次做法：在昨天代码的基础上修改

1. 计算普通子数组的最大和
   使用动态规划计算以每个位置为起点的最大子数组和（存储在 val 中），并更新全局最大值 rightmax。
2. 计算后缀和与前缀和
   sum[i]：从位置 i 到数组末尾的元素和。
   left[i]：从数组开头到位置 i 的元素和。
3. 处理环形情况
   对于每个可能的分割点 j，计算环形子数组的最大和：
   将数组分成两部分：[0, j] 和 [j+1, n-1]。
   环形子数组的和为 left[j] + max(右侧后缀和)，其中右侧后缀和通过遍历 sum 数组计算

class Solution {public int maxSubarraySumCircular(int[] nums) {int[] val = new int[nums.length*2];int[] sum = new int[nums.length];int[] left = new int[nums.length];int rightmax=nums[nums.length-1];val[nums.length-1]=nums[nums.length-1];for(int i= nums.length-2;i>=0;i--){int x=val[i+1]+nums[i];if(x>nums[i]){val[i]=x;}else{val[i]=nums[i];}if(val[i]>rightmax){rightmax=val[i];}}sum[nums.length-1]=nums[nums.length-1];for (int i = nums.length-2; i>=0; i--) {sum[i]=nums[i]+sum[i+1];}left[0]=nums[0];for (int i = 1; i < nums.length; i++) {left[i]=left[i-1]+nums[i];}for(int i=nums.length;i<nums.length*2-1;i++){int j=i%nums.length;int max=-1000;for(int k=nums.length-1;k>j;k--){max=Math.max(max,sum[k]);}val[i]=max+left[j];if(val[i]>rightmax){rightmax=val[i];}}return rightmax;}
}

超时了

优化思路：

1. 使用 Kadane 算法：维护一个变量pre，记录以当前元素结尾的最大子数组和，同时更新全局最大和res。
   预处理最大前缀和数组leftMax
   leftMax[i] 表示从数组开头到索引i的最大前缀和。
   例如，数组[1, -2, 3]的leftMax为[1, 1, 2]（前缀和分别为1, -1, 2，取最大值）。
2. 枚举后缀并结合最大前缀
   从右向左遍历数组，累加后缀和rightSum。
   对于每个位置i，环形子数组的最大和为 当前后缀和 + 之前的最大前缀和（即rightSum + leftMax[i-1]）。
   结果比较
   最终结果取普通子数组的最大和与环形子数组的最大和中的较大值。

class Solution {public int maxSubarraySumCircular(int[] nums) {if(nums.length==0){return 0;}int nos=no(nums);int[]left=new int[nums.length];left[0]=nums[0];int leftsum=nums[0];for(int i=1;i<nums.length;i++){leftsum+=nums[i];left[i]=Math.max(left[i-1],leftsum);}//求最大前缀和int rightsum=0;int max=-100000;for(int i=nums.length-1;i>0;i--){rightsum+=nums[i];max=Math.max(max,rightsum+left[i-1]);//拆为前缀＋后缀}return Math.max(nos,max);}public int no(int[]nums){//处理不用环的最大子数组和int leftmax=nums[0];int leftbe=nums[0];for(int i=1;i<nums.length;i++){int x=leftbe+nums[i];if(x>nums[i]){leftbe=x;}else{leftbe=nums[i];}if(leftbe>leftmax){leftmax=leftbe;}}return leftmax;}
}