网站开发定制模板网站建设,做网站找酷万,网站建设题目,创建公司网站免费一. 连续和最大子数组 给你一个整数数组 nums #xff0c;请你找出一个具有最大和的连续子数组#xff08;子数组最少包含一个元素#xff09;#xff0c;返回其最大和。 子数组 是数组中的一个连续部分。 示例 1#xff1a; 输入#xff1a;nums [-2,1,-3,4,-1,2,1,-5,…一. 连续和最大子数组 给你一个整数数组 nums 请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。 子数组 是数组中的一个连续部分。 示例 1 输入nums [-2,1,-3,4,-1,2,1,-5,4] 输出6 解释连续子数组 [4,-1,2,1] 的和最大为 6 。 示例 2 输入nums [1] 输出1 示例 3 输入nums [5,4,-1,7,8] 输出23 1.1 怎么想到使用动态规划
当然是题目给的建议。
题目中讲求最大和。题目中讲返回最大和。
我们要做的是求一个目标值通常最大最小 不要求过程只要结果。 对于这种题目我们通常使用动态规划。
1.2 动态规划第一步该做什么
首先明确几个关键点。
最大连续子数组与子序列区别开即数组下标连续。和最大针对每个【i】怎么计算子问题。
当然就是找到状态转移方程啊 f ( i ) { f ( i − 1 ) i ( i f ( i − 1 ) i ) i ( i f ( i − 1 ) i ) f(i) \left\{ \begin{aligned} f(i-1) i (i f(i-1) i) \\ i (i f(i-1) i) \end{aligned} \right. f(i){f(i−1)i(if(i−1)i)i(if(i−1)i)
求和的状态转移方程很简单。当我们有了 i - 1位置的结果去求 i位置的连续子数组和当然就是用 f ( i − 1 ) i 和 i f(i-1) i 和 i f(i−1)i和i 比较一下拿最大的呀
仔细想想这不对吧 这有什么不对的呢 明显前4个最大连续和是 1 2 3 6。
所以错在哪里了呢或者说我们怎么计算能得到6呢
…
很简单return 2 6 ? 2 : 6 不就行了吗
我们的函数计算的值是以当前坐标为结尾的数组的最大子数组。 动态规划的子问题和整体问题求的目标是一致的只有状态再更迭此处的状态就是下标index。
计算得到函数要与旧的最大值进行比较取最大。
fun maxSubArray(nums []int) int {pre, res : 0, nums[0]for _, v : range nums {pre max(pre v, v)res max(res, pre)}return res
}二. 连续乘积最大子数组 给你一个整数数组 nums 请你找出数组中乘积最大的非空连续子数组该子数组中至少包含一个数字并返回该子数组所对应的乘积。 测试用例的答案是一个 32-位 整数。 子数组 是数组的连续子序列。 示例 1: 输入: nums [2,3,-2,4] 输出: 6 解释: 子数组 [2,3] 有最大乘积 6。 示例 2: 输入: nums [-2,0,-1] 输出: 0 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。 2.1 这个题目使用什么方法
乘积最大。返回乘积。连续子数组。
这俩题目是不是一样的。先想一想差别。
求最大值返回结果 那使用动态规划没什么问题。
2.2 直接写代码
fun maxSubArray(nums []int) int {pre, res : 1, nums[0]for _, v : range nums {pre max(pre * v, v)res max(res, pre)}return res
}因为乘法所以pre初始值改为1 。
会有问题吗 明显的错误…
只是加法变乘法原来的方案就行不通了。
问题就在于乘法遇到负数从最大变成了最小-4 * 3 -12
所以我们需要对这个负号进行一下特殊的处理。
2.3 状态该怎么变化呢
如果遇到负数我们希望使用一个最小的值与其做乘积运算期望得到一个最大的值 反之遇到正数我们要用一个最大的值进行乘积运算。
所以我们需要记两个值分别是一个最大的preMax 和一个最小的preMin. p r e M a x f ( i ) m a x p r e M i n f ( i ) m i n p r e M a x M a x ( f ( i − 1 ) m a x ∗ n u m [ i ] , f ( i − 1 ) m i n ∗ n u m [ i ] , n u m [ I ] ) p r e M i n M i n ( f ( i − 1 ) m i n ∗ n u m [ i ] , f ( i − 1 ) m a x ∗ n u m [ i ] , n u m [ I ] ) preMax f(i)_{max} \\ preMin f(i)_{min}\\ preMax Max(f(i-1)_{max}*num[i], f(i-1)_{min} * num[i], num[I])\\ preMin Min(f(i-1)_{min}*num[i], f(i-1)_{max} * num[i], num[I]) preMaxf(i)maxpreMinf(i)minpreMaxMax(f(i−1)max∗num[i],f(i−1)min∗num[i],num[I])preMinMin(f(i−1)min∗num[i],f(i−1)max∗num[i],num[I])
代码就比较简单了
func maxProduct(nums []int) int {preMax,preMin, res : 1,1, nums[0]for _,v : range nums {mn,mx : preMin,preMaxpreMax max(mx * v, max(mn * v,v))preMin min(mn * v, min(mx * v,v))res max(preMax,res)}return res为什么多了一行mn,mx : preMin,preMax 你可以去掉试试看~
20230902记录今天先到这里。
