莱西做网站公司,哪个网站可以搭建网页,网站的广度,网站开发需要用到哪些软件目录 一.题目
二.解题思路
三.解题代码 一.题目 918. 环形子数组的最大和
给定一个长度为 n 的环形整数数组 nums #xff0c;返回 nums 的非空 子数组 的最大可能和 。
环形数组 意味着数组的末端将会与开头相连呈环状。形式上#xff0c; nums[i] 的下一个元素是 nums[…目录 一.题目
二.解题思路
三.解题代码 一.题目 918. 环形子数组的最大和
给定一个长度为 n 的环形整数数组 nums 返回 nums 的非空 子数组 的最大可能和 。
环形数组 意味着数组的末端将会与开头相连呈环状。形式上 nums[i] 的下一个元素是 nums[(i 1) % n] nums[i] 的前一个元素是 nums[(i - 1 n) % n] 。
子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。形式上对于子数组 nums[i], nums[i 1], ..., nums[j] 不存在 i k1, k2 j 其中 k1 % n k2 % n 。 示例 1
输入nums [1,-2,3,-2]
输出3
解释从子数组 [3] 得到最大和 3示例 2
输入nums [5,-3,5]
输出10
解释从子数组 [5,5] 得到最大和 5 5 10示例 3
输入nums [3,-2,2,-3]
输出3
解释从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3提示
n nums.length1 n 3 * 104-3 * 104 nums[i] 3 * 104
二.解题思路
动态规划解法 g[i] 表示以i位置为结尾的所有子数组的最小和 环形数组的子数组的最大和有两种情况 1.拥有最大和的子数组就在数组的中间 2.环形数组的头部和尾部共同组成了拥有最大和的子数组 我们只需要求两种情况的最大值再确定哪种更大返回即可 对于1 f[i] 表示以i位置为结尾的所有子数组的最大和 当长度为1时子数组的最大和为nums[i] 当长度大于1时子数组的最大和nums[i]f[i-1] 状态转移方程 f[i]Math.max(nums[i],f[i-1]); 对于2 转化为求数组中间的最小子数组和用数组总和sum-数组中间的最小子数组和(gmin) 同理: 最小和的状态转移方程 g[i]Math.min(nums[i],g[i-1]); 初始化可以添加一个虚拟的头部在状态数组里多开一个空间填入0 可以使填了0可以使原来的结果不变f[0]g[0]0, 循环填状态方程时就可以直接从1开始状态数组多加了一个格子注意下标映射 原数组nums[i]变成nums[i-1] 返回值注意如果数组全部为负数如 [-1,-2,-3], 那么最大的子数组应该在数组中间直接返回fmax 三.解题代码
public int maxSubarraySumCircular(int[] nums) {int nnums.length;int[] fnew int[n1];int[] gnew int[n1];int fmaxInteger.MIN_VALUE;int gminInteger.MAX_VALUE;int sum0;for(int i1;in;i){sumnums[i-1]; //求总数组和f[i] Math.max(nums[i-1],nums[i-1] f[i-1]);fmax Math.max(fmax,f[i]);//求数组中间的最大子数组和g[i] Math.min(nums[i-1],nums[i-1] g[i-1]);gmin Math.min(gmin,g[i]);//求数组中间的最小子数组和} //判断数组是否全为负数如果是直接返回fmax,不是判断12情况哪个大return sumgmin ? fmax:Math.max(fmax,sum-gmin);}
}
