这道题,比较有意思,他们说用c++的Map会好些很多,而且节省空间,奈何我不会啊(有兴趣的道友,而可自行实现)。

  一道递推的题目,因t为不会c++的Map所以我只能用数组来实现,但是有负数啊,数组索引不能为负数啊,这可怎么办凉凉了。简单暴力的方法,直接加上最大边界值,数组开两倍大,相当于去掉了符号。这时候我们就可以开出我们的dp数组了。既然是递推那么就得有 递推公式 。也很简单, 最长啥啥啥的那不就是步长为 1 一次次累加的关系吗?而且还要最长,那肯定得要有max函数了。我们设dp[i]表示当前序列最后一个数是i的最大子序列长度,每一次i++之后我们都与上一次认定的“最长值”进行比较,如果中间断开,那么由于上一次的“最长值” 的索引由步长决定,且步长为固定值,所以断开后会自动重新计数。有这个规律我们可以很轻易的写出状态转移方程

dp[i]=max(dp[i],dp[i-difference]+1);

  当然这仅仅是动态转移方程,具体实现起来还是需要改动的。大家可以自己先试试如何实现,再来看代码。

 1 /**
 2  * @brief  最长定差子序列
 3  * @note   一定要加10000
 4  * @param  arr: 给定序列
 5  * @param  arrSize: 序列长度
 6  * @param  difference: 定固差
 7  * @author 杨文蓁的小迷弟
 8  */
 9 int longestSubsequence(int* arr, int arrSize, int difference){
10     int ans = 0;
11     int dp[20002] = {0};
12     for (int i = 0; i < arrSize; i++)
13     {
14         arr[i] += 10000;
15     }
16
17     for (int i = 0; i < arrSize; i++)
18     {
19         int sum = arr[i] - difference;
20         if (sum > 20000 || sum < 0)
21         {
22             dp[arr[i]] = 1;
23         }
24         else
25         {
26             dp[arr[i]] = dp[arr[i]] > (dp[sum]+1) ? dp[arr[i]] : (dp[sum]+1);
27         }
28         ans = ans > dp[arr[i]] ? ans : dp[arr[i]];
29         printf("%d\n", ans);
30     }
31
32     return ans;
33 }
View Code

  周赛不易,诸君共勉!

02-14 02:11