2407. 最长递增子序列 II-动态规划暴力解法和线段树

给你一个整数数组 nums 和一个整数 k 。

找到 nums 中满足以下要求的最长子序列：

子序列 严格递增
子序列中相邻元素的差值 不超过 k 。
1
2

请你返回满足上述要求的 最长子序列 的长度。

子序列 是从一个数组中删除部分元素后，剩余元素不改变顺序得到的数组。

示例 1：

输入：nums = [4,2,1,4,3,4,5,8,15], k = 3
输出：5
解释：
满足要求的最长子序列是 [1,3,4,5,8] 。
子序列长度为 5 ，所以我们返回 5 。
注意子序列 [1,3,4,5,8,15] 不满足要求，因为 15 - 8 = 7 大于 3 。

示例 2：

输入：nums = [7,4,5,1,8,12,4,7], k = 5
输出：4
解释：
满足要求的最长子序列是 [4,5,8,12] 。
子序列长度为 4 ，所以我们返回 4 。

示例 3：

输入：nums = [1,5], k = 1
输出：1
解释：
满足要求的最长子序列是 [1] 。
子序列长度为 1 ，所以我们返回 1 。

动态规划暴力解法如下：

int lengthOfLIS(int* nums, int numsSize, int k){
    int dp[numsSize];
    dp[0]=1;
    int max=1;
     for(int i=1;i<numsSize;i++){
         dp[i]=1;
         for(int j=0;j<i;j++){
             if(nums[i]-nums[j]<=k&&nums[i]>nums[j]){
                 
                   dp[i]=fmax(dp[j]+1,dp[i]);

             }
           
         }
         printf("%d ",dp[i]);
         max=fmax(dp[i],max);
     }
     return max;

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

线段树解法如下，但是下面这个线段是时无序线段树，比上面这个暴力解法好很多，但是还是时间上还是差了一些：
这题对于c语言求解不是很友好，一个不错的方法就是用分段哈希法，可以不错的解决这个问题：

struct segment_tree{
    struct tree *left;
    struct tree *right;
    int index;
    int max_index;
    int min;
    int max;

};


void creat_segment_tree(struct segment_tree **root,int *a,int low,int high){
    if(low==high){
        (*root)->max=a[low];
        (*root)->min=a[low];
        (*root)->index=low;
         (*root)->max_index=low;
       
        (*root)->left=NULL;
        (*root)->right=NULL;
       


    }
    else if(high>low){
         int max=a[low];
     
        int min=a[low];
        for(int i=low+1;i<=high;i++){
            if(a[i]>max){
                max=a[i];
               
            }
            if(a[i]<min){
                min=a[i];
            }
        }
        int mid=(low+high)/2;
        (*root)->max=max;
        (*root)->min=min;
        (*root)->index=low;
        (*root)->max_index=high;
        (*root)->left=(struct segment_tree *)malloc(sizeof(struct segment_tree ));
        (*root)->right=(struct segment_tree *)malloc(sizeof(struct segment_tree ));
        creat_segment_tree(&((*root)->left),a,low,mid);
        creat_segment_tree(&((*root)->right),a,mid+1,high);

    }
    else{
        (*root)=NULL;
    }
   
    
}

void  pre_dfs(struct segment_tree *root){
    if(root){
        
       // printf("%d  %d|",root->max,root->min);
        pre_dfs(root->left);
        pre_dfs(root->right);

    }
}


void  find(struct segment_tree *root,int *max_t,int index,int val,int k,int *dp){
    if(root){
      //  printf("%d %d->",root->max,root->index);

  
        if(root->left==NULL&&root->right==NULL&&root->index<index&&root->max<val&&val-root->max<=k){

            *max_t=fmax(dp[root->index]+1,*max_t);
        }
        else{
            if(root->index<index&&val-root->max<=k&&root->min<val){
              
           
                     find(root->right,max_t,index,val,k,dp);
                    find(root->left,max_t,index,val,k,dp);

          
                     
                      
            }

        }
      }
    


}

int lengthOfLIS(int* nums, int numsSize, int k){
    
     int max=1;
     int *max_t=(int *)malloc(sizeof(int));
     int *dp=(int *)malloc(sizeof(int)*numsSize);
     int size=1;
     int pre=nums[0];
    
     for(int i=1;i<numsSize;i++){
         if(nums[i]==pre){
             continue;
         }
         else{
             pre=nums[i];
             nums[size++]=nums[i];
         }
     }
    
     numsSize=size;
     
    
     
      struct tree *root=(struct segment_tree *)malloc(sizeof(struct segment_tree ));
     creat_segment_tree(&root,nums,0,numsSize-1);
    pre_dfs(root);
    
   
     


    dp[0]=1;
    
    
     for(int i=1;i<numsSize;i++){
         *max_t=1;
        find(root,max_t,i,nums[i],k,dp);
         dp[i]=*max_t;
     //    printf("dp %d ",dp[i]);
         
       
         max=fmax(dp[i],max);
     }
     return max;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142