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

• 等差数列划分

  如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。例如，[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
}