东莞企业模板建站,网站开发流程书籍,做最好的导航网站,网站建设徐州1027. 最长等差数列
给你一个整数数组 nums#xff0c;返回 nums 中最长等差子序列的长度。
回想一下#xff0c;nums 的子序列是一个列表 nums[i1], nums[i2], …, nums[ik] #xff0c;且 0 i1 i2 … ik nums.length - 1。并且如果 seq[i1] - …1027. 最长等差数列
给你一个整数数组 nums返回 nums 中最长等差子序列的长度。
回想一下nums 的子序列是一个列表 nums[i1], nums[i2], …, nums[ik] 且 0 i1 i2 … ik nums.length - 1。并且如果 seq[i1] - seq[i]( 0 i seq.length - 1) 的值都相同那么序列 seq 是等差的。
示例 1 输入nums [3,6,9,12] 输出4 解释 整个数组是公差为 3 的等差数列。
示例 2 输入nums [9,4,7,2,10] 输出3 解释最长的等差子序列是 [4,7,10]。
示例 3 输入nums [20,1,15,3,10,5,8] 输出4 解释最长的等差子序列是 [20,15,10,5]。
提示 2 nums.length 1000 0 nums[i] 500
动态规划
如果开数组会爆只能开容器。 dp[i][j]表示第i个元素及前面元素的公差为j的最长等差数列的长度因为公差范围最小可以到-500于是每个公差进行处理500使其非负。
class Solution {
public:int longestArithSeqLength(vectorint nums) {vectorvectorint dp(1005,vectorint(1001,0));int res0;int lennums.size();for(int i1;ilen;i){for(int j0;ji;j){int knums[i]-nums[j]500;if(dp[j][k]1dp[i][k]) dp[i][k]dp[j][k]1;if(dp[i][k]res) resdp[i][k];}}return res1;}
};
