数据结构和算法-数组动态规划

等差数列划分如果一个数列 至少有三个元素 ,并且任意两个相邻元素之差相同,则称该数列为等差数列。例如,[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。给你一个整数数组 nums ,返回数组 nums 中所有为等差数组的 子数组 个数。子数组 是数组中的一个连续序列。最佳观光组合给你一个正整数数组 values,其中 values[i] 表示第 i 个观光景点的评分,并且两个景点 i 和 j 之间的 距离 为 j - i。一对景点(i < j)组成的观光组合的得分为 values[i] + values[j] + i - j ,也就是景点的评分之和 减去 它们两者之间的距离。返回一对观光景点能取得的最高分。等差数列划分解题思路定义等差数列 一个数列 至少有三个元素 ,并且任意两个相邻元素之差相同,则称该数列为等差数列 取数组第一,二个元素先求出公差,从数组下标2开始迭代,判断当前元素和前一个元素的差是否等于公差,若等于则计数,如果不是重新计算公差,然后计数器清零。每次计算总数代码实现func numberOfArithmeticSlices(nums []int) int { if len(nums)<3{ return 0 } tolerance:=nums[1]-nums[0] total,count:=0,0 for i:=2;i<len(nums);i++{ if nums[i]-nums[i-1]==tolerance{ total++ }else{ tolerance=nums[i]-nums[i-1] total=0; } count+=total } return count}最佳观光组合解题思路定义等差数列 观光组合的得分为 values[i] + values[j] + i - j 代码实现func maxScoreSightseeingPair(values []int) int { a,b,max:=0,1,0 for b<len(values) { pre:=values[a]+a-b max = MathMax(max,pre+values[b]) if values[b]>pre{ a=b } b++ } return max}func MathMax(a,b int)int{ if a>b{ return a } return b}