递增数组题解

因为我们要求得一个单调递增的序列，那么我们如果要选择一个区间的话这个区间必为后缀，不然我们选择一个中间的区间相当于把中间提高了，那么对后面就造成了不利的影响。所以我们只需要看每一个位置i与后面的一个元素i+1的差，位置i的贡献为max(0,array[i]+1-array[i+1])。时间复杂度O(n),空间复杂度O(n)。

class Solution {
public:
    /**
     * 
     * @param array int整型一维数组 array
     * @param arrayLen int array数组长度
     * @return long长整型
     */
    long long IncreasingArray(int* array, int arrayLen) {
        // write code here
        long long ans=0;
        for(int i=0;i<arrayLen-1;i++)
            ans+=max(0,array[i]+1-array[i+1]);
        return ans;
    }
};