Leetcode 1218. 最长定差子序列（DAY 47） ---- 动态规划学习期（昨天又没有看书捏 懒狗biss）

原题题目

代码实现（首刷自解超时 ?)

int longestSubsequence(int* arr, int arrSize, int difference){
    int* dp = (int*)malloc(sizeof(int) * (arrSize+1)),i,j,max = 1;dp[0] = 1;for(i=1;i<arrSize;i++){
    dp[i] = 1;for(j=0;j<i;j++){
    if(arr[i] == arr[j] + difference)dp[i] = fmax(dp[i],dp[j] + 1);}max = fmax(dp[i],max);}return max;
}

代码实现（首刷改良 空间换时间）

int longestSubsequence(int* arr, int arrSize, int difference){
    int dp[40001] = {
    0},max = 0,i,temp;for(i=0;i<arrSize;i++){
    temp = arr[i] + 20000;dp[temp] = 1;dp[temp] = fmax(dp[temp],dp[temp-difference]+1);max = fmax(dp[temp],max);}return max;
}