细节上的问题

记录一下今天在写最长上升子序列上遇到的一个细节处理上面的问题
先看两段代码

/*
a存放序列
f[i] 表示以第i个数结尾的最长上升子序列
*/ 

// 第一段
f[1] = 1; // 初始化
for (int i = 2;i <= n;i ++ ){
    for (int j = 1;j < i;j ++ ){
        if (a[i) >= a[j]) f[i] = max(f[i], f[j] + 1);
    }
}
// 第二段
a[0] = 0;
for (int i = 1;i <= n; i ++ ){
    for (int j = 0;j < i;j ++ ){
        if (a[i] >= a[j]) f[i] = max(f[i], f[j] + 1);
    }
}

这两段代码第一段是错的，第二段是对的

分析

第一段是根据 1~i-1 这段的f[j]求出f[i]
第二段是根据 0~i 这段的f[j]求出f[i]
就差f[0]这一个为什么就导致结果错了呢？
原因就是序列a中第i个数a[i]小于a[j]所有值，这样的话f[i]就没有计算到，默认为0，实际上为1，对最后结果可能就会造成影响