1. 题意

给定一个数组，连续一个或多个，满足 : (前一位比后一位大1)

a[i]=a[i−1]−1

求构成的段数

样例：3,2,1,4

输出：7

解释：[3], [2], [1], [4], [3,2], [2,1] 和 [3,2,1]

2. 算法

动态规划

3. 思路

定义 dp[i] ，表示以第 i 位结束的满足条件的段数。

则 dp[0] = 1 , 对于 i > 0， 分下列两种情况：

a[i] != a[i - 1] - 1

连续一个，dp[i] = 1

a[i] == a[i - 1] - 1

那么第 i - 1 天为结尾的段数可以与第 i 天继续构成平滑下跌段数。即，dp[i] = dp[i - 1] + 1

由于对 dp 数组的定义，最终答案就是每一位的 dp 之和，即每一位都作为结尾能够成的段数。

分析发现： dp[i] 只依赖于 dp[i - 1] ， 所以可以用一个变量 len 来维护当前的 dp 值，一个变量 ans 来维护 dp 数组之和。

代码

class Solution {
public:
    long long getDescentPeriods(vector<int>& prices) {
        long long ans = 1, len = 1;
        for (int i = 1; i < prices.size(); i++) {
            len = prices[i] == prices[i - 1] - 1 ? len + 1 : 1;
            ans += len;
        }
        return ans;
    }
};