本文主要是介绍力扣918-环形子数组的最大和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
清晰易懂版。
package likou;import java.util.Arrays;/** 环形子数组的最大和* 题干：* 给定一个由整数数组 A 表示的环形数组 C，求 C 的非空子数组的最大可能和* 这里肯定是有一个隐含条件的，那就是数组元素要连续，不然直接对数组遍历，找到所有的正数即可*/
public class Demo918 {/** 解题思路：* 找到子数组的最大和，只有两种可能性* 可能性1：最大和在nums[0]到nums[nums.length-1]之间，即不需要用到环，用动态规划来做* 可能性2：最大和可能存在环，即使最大和子数组包含nums[0]和nums[nums.length-1]两个元素* 这种情况就意味着数组成为了一个环，要想找到最大和的子数组，只需要将数组所有元素的和累加* 然后减去最小和的子数组，就可以得到最大和（相当于是一个环，用刀从中劈开，就剩下两个部分，一个最大，* 则另一个最小）*/public int maxSubarraySumCircular(int[] nums) {int max1 = nums[0];int sum = 0;int temp1 = 0;//计算不需要用到环的最大和for(int i=0;i<nums.length;i++) {sum = sum+nums[i];temp1 = Math.max(temp1+nums[i], nums[i]); if(max1 < temp1) {max1 = temp1;}}//计算需要用到环的最大和int temp2 = 0;int min = 0;if(nums.length>2) {min = nums[1];for(int k=1;k<nums.length -1;k++) {temp2 = Math.min(temp2+nums[k],nums[k]);if(temp2 < min) {min = temp2;}}}return Math.max(max1, sum-min);}public static void main(String args[]) {Demo918 demo = new Demo918();int[] nums = {2,-2,2,7,8,0};System.out.println(demo.maxSubarraySumCircular(nums));}
}
这篇关于力扣918-环形子数组的最大和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
