企业官网建设流程全解析

门窗网站设计,网站漂浮怎么做,网站的域名能换吗,泉州网站建设哪里好918. 环形子数组的最大和 问题描述 给定一个环形整数数组 nums#xff08;即数组的末端将会与开头相连#xff09;#xff0c;返回非空子数组的最大可能和。 注意#xff1a;环形数组意味着数组可以首尾相连#xff0c;因此子数组可以跨越数组的末尾和开头。 示例#xf…918. 环形子数组的最大和问题描述给定一个环形整数数组nums即数组的末端将会与开头相连返回非空子数组的最大可能和。注意环形数组意味着数组可以首尾相连因此子数组可以跨越数组的末尾和开头。示例输入: nums [1,-2,3,-2] 输出: 3 解释: 子数组 [3] 的和最大。 输入: nums [5,-3,5] 输出: 10 解释: 子数组 [5,5] 的和最大跨越末尾和开头。 输入: nums [-3,-2,-3] 输出: -2 解释: 子数组 [-2] 的和最大。算法思路两种情况非环形情况最大子数组完全在数组内部不跨越边界使用经典的 Kadane 算法环形情况最大子数组跨越数组末尾和开头等价于总和减去最小子数组的和跨越边界的子数组 整个数组 - 中间的最小子数组代码实现方法一Kadane算法classSolution{/** * 计算环形数组中非空子数组的最大和 * * param nums 环形整数数组 * return 非空子数组的最大可能和 */publicintmaxSubarraySumCircular(int[]nums){// 使用Kadane算法计算最大子数组和intmaxSumkadaneMax(nums);// 计算数组总和inttotalSum0;for(intnum:nums){totalSumnum;}// 使用Kadane算法计算最小子数组和intminSumkadaneMin(nums);// 特殊情况如果所有元素都是负数minSum totalSum// 此时环形情况会得到 totalSum - minSum 0需要非空子数组// 所以直接返回 maxSum即最大的单个元素if(totalSumminSum){returnmaxSum;}// 返回非环形情况和环形情况的最大值returnMath.max(maxSum,totalSum-minSum);}/** * Kadane算法计算最大子数组和 */privateintkadaneMax(int[]nums){intmaxSoFarnums[0];intmaxEndingHerenums[0];for(inti1;inums.length;i){// 要么扩展之前的子数组要么重新开始maxEndingHereMath.max(nums[i],maxEndingHerenums[i]);maxSoFarMath.max(maxSoFar,maxEndingHere);}returnmaxSoFar;}/** * Kadane算法变种计算最小子数组和 */privateintkadaneMin(int[]nums){intminSoFarnums[0];intminEndingHerenums[0];for(inti1;inums.length;i){// 要么扩展之前的子数组要么重新开始minEndingHereMath.min(nums[i],minEndingHerenums[i]);minSoFarMath.min(minSoFar,minEndingHere);}returnminSoFar;}}方法二一次遍历classSolution{/** * 一次遍历计算最大子数组和、最小子数组和和总和 * * param nums 环形整数数组 * return 非空子数组的最大可能和 */publicintmaxSubarraySumCircular(int[]nums){intmaxSumnums[0];// 最大子数组和intminSumnums[0];// 最小子数组和intmaxEndingHerenums[0];// 当前最大子数组和intminEndingHerenums[0];// 当前最小子数组和inttotalSumnums[0];// 数组总和for(inti1;inums.length;i){intnumnums[i];totalSumnum;// 更新最大子数组和maxEndingHereMath.max(num,maxEndingHerenum);maxSumMath.max(maxSum,maxEndingHere);// 更新最小子数组和minEndingHereMath.min(num,minEndingHerenum);minSumMath.min(minSum,minEndingHere);}// 特殊情况处理所有元素都是负数if(totalSumminSum){returnmaxSum;}returnMath.max(maxSum,totalSum-minSum);}}算法分析时间复杂度O(n)只需要遍历数组一次或两次空间复杂度O(1)只使用常数个额外变量算法过程输入nums [5,-3,5]计算非环形最大子数组和[5] 5,[5,-3] 2,[5,-3,5] 7,[-3] -3,[-3,5] 2,[5] 5最大值 7计算总和5 (-3) 5 7计算最小子数组和最小子数组是[-3]和为-3环形最大子数组和 总和 - 最小子数组和 7 - (-3) 10最终答案 max(7, 10) 10输入nums [-3,-2,-3]非环形最大子数组和 -2总和 -8最小子数组和 -8整个数组由于总和 最小子数组和返回非环形结果-2测试用例publicstaticvoidmain(String[]args){SolutionsolutionnewSolution();// 测试用例1标准示例int[]nums1{1,-2,3,-2};System.out.println(Test 1: solution.maxSubarraySumCircular(nums1));// 3// 测试用例2环形情况更优int[]nums2{5,-3,5};System.out.println(Test 2: solution.maxSubarraySumCircular(nums2));// 10// 测试用例3全负数int[]nums3{-3,-2,-3};System.out.println(Test 3: solution.maxSubarraySumCircular(nums3));// -2// 测试用例4全正数int[]nums4{1,2,3,4};System.out.println(Test 4: solution.maxSubarraySumCircular(nums4));// 10// 测试用例5单元素int[]nums5{5};System.out.println(Test 5: solution.maxSubarraySumCircular(nums5));// 5// 测试用例6两元素int[]nums6{-2,-3};System.out.println(Test 6: solution.maxSubarraySumCircular(nums6));// -2// 测试用例7复杂环形情况int[]nums7{3,-1,2,-1};System.out.println(Test 7: solution.maxSubarraySumCircular(nums7));// 4// 非环形[3,-1,2] 4环形[2,-1,3] 4// 测试用例8另一个复杂情况int[]nums8{3,-2,2,-3};System.out.println(Test 8: solution.maxSubarraySumCircular(nums8));// 3// 非环形[3] 3环形[2,-3,3] 2// 测试用例9大数值int[]nums9{10000,-10000,10000};System.out.println(Test 9: solution.maxSubarraySumCircular(nums9));// 20000// 测试用例10交替正负int[]nums10{1,-1,1,-1,1};System.out.println(Test 10: solution.maxSubarraySumCircular(nums10));// 3// 环形[1,-1,1,-1,1] 全部 1或者 [1,1,1] 跨越 3}关键点两种情况非环形标准的最大子数组问题环形相当于找最小子数组然后用总和减去它特殊情况处理当所有元素都是负数时最小子数组就是整个数组Kadane算法不仅可以求最大子数组也可以求最小子数组核心思想是动态规划每个位置要么开始新的子数组要么扩展之前的子数组数学环形最大子数组 中间最小子数组 整个数组环形最大子数组 总和 - 最小子数组常见问题为什么不能直接用环形情况当所有元素都是负数时环形情况会错误地返回0