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;}
}