求最长等差数列（动态规划）

最新推荐文章于 2025-04-15 14:42:47 发布

一念执着_

最新推荐文章于 2025-04-15 14:42:47 发布

阅读量2.2k

点赞数 2

分类专栏： ======动态规划====== 文章标签：动态规划 DP

本文链接：https://blog.csdn.net/Gengman/article/details/51417026

版权

该博客探讨了如何使用动态规划方法找到一个整数数组中最长的等差数列子序列。博主首先指出，问题允许不按原数组顺序选取，因此可以先对数组进行排序。接着，介绍了Problem J：Arithmetic Sequence的题目背景、输入输出格式，并提供了样例输入和输出。博主还给出了提示，在第一个样例中，应该选择1,3,5,7来形成一个长度为4的等差数列。" 108761685,7393299,C++设计模式解析：代理模式（Proxy Pattern）,"['设计模式', 'C++', '代理模式', '软件设计']

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

给你n个数，求出其最长的等差数列的子序列。

首先问题并没有要求要按照原来数组的顺序，所以可以先对该数组排序

1. 如果不要求该最长子序列中的元素是相邻的话，可以用一个简单的DP来完成。算法的复杂度是O( n^ 2)。

模板

const int MAX=1010;
int dp[MAX][MAX];//dp[i][j]以i为结尾的某子序列（该子序列的公差为j）的最大长度
int n;//n个数
int a[MAX];//大小为n的数列
int longestSubSeq(int a[])
{
	int s=n;
	if (s <= 1) return s;

	sort(a,a+n);//可以在主函数里排序

	int ans=1;
	int i,j;
	for(i=0;i<MAX;i++)
		for(j=0;j<MAX;j++)
			dp[i][j]=1; //单独成列

	for(i=1;i<n;i++)
	{
		for(j=0;j<i;j++)
		{
			int d=a[i]-a[j];//d为公差
			dp[i][d]=dp[j][d]+1;
			ans=max(ans,dp[i][d]);
		}
	}
	return ans;
}

下面是一个求最长等差子序列的题

题目连接