leetcode 1014. 最佳观光组合 C语言 动态规划

分析题目

将所求部分分为两部分 values[i]+values[j]+i-j = (values[i]+i)+(values[j]-j)

可以假定j是固定的，即(values[j]-j)是固定的，这里先不管j，题目中要求i

运用动态规划

设计状态：求第i项前面的最大值（包含第i项）就转移到求【第i-1项之前的最大值（包含第i-1项）与第i项之间】的最大值

写出状态方程：Rmix[i]=max(Rmix[i-1],a[i]+i);

设定初始状态:Rmix[0]=a[0];        maxn=rmix[0]+values[1]+1;

执行状态转移

返回最终解 

int max(int a,int b)                        //定义一个求最大值的函数
{
    return a>b?a:b;
}

void PreMax(int* a,int n,int*Premax)        //定义一个求前缀最大值的函数
{
    int i;
    for(i=0;i 
执行结果 
 
 
 
 
 
 时间复杂度和空间复杂度分析 
 
代码共执行2n-1次，因此时间复杂度为O（n）
 
 
分配了一个数组，因此空间复杂度为O（n）
 
 
 
 总结 
 
1 - 灵活处理问题，要假定右端是固定的，问题就变成了在左闭右开前缀最大值的问题
 
 
2 - 初始状态的设定，不要漏掉i，j