学步园

http://haixiaoyang.wordpress.com/category/dynamic-programming/

http://www.51nod.com/question/index.html#!questionId=79

在一个升序排列好的数列里面找到最长的等差数列

例子：1 3 5 6 8 9 10 12 13 14
子数列有(两项的不在列举）
1 3 5
1 5 9 13
3 6 9 12
3 8 13
5 9 13
.....

得出的最长的等差数列应该是：6 8 10 12 14

方案1：

用hash

遍历所有可能的差值d

   hash表中记录的是到当前为止，以之前的数字为结尾的等差数列的最长长度

   对一个新的元素，将其减去d之后，查找是否有相同的值，如果存在，则替换为这个新元素，并将值加1

public static void Solve1(int[] items)
{
    Dictionary hash = new Dictionary();
    int max = items.Max() - items.Min();
    int maxLength = 2, maxInc = -1, last = -1;
 
    for (int inc = 1; inc < max; inc++)
    {
        if (inc * maxLength > max)
            break;
 
        hash.Clear();
        hash.Add(items[0], 1);
 
        for (int i = 1; i < items.Length; i++)
        {
            if (hash.ContainsKey(items[i] - inc))
            {
                int value = hash[items[i] - inc];
                hash.Remove(items[i] - inc);
                hash.Add(items[i], value + 1);
 
                if (value + 1 > maxLength)
                {
                    maxLength = value + 1;
                    maxInc = inc;
                    last = items[i];
                }
            }
            else if (!hash.ContainsKey(items[i]))
                hash.Add(items[i], 1);
        }
    }
 
    Console.WriteLine("{0} {1} {2}", maxLength, maxInc, last);
}

方法2：

//Find the length of the longest arithmetic progression sequence of a sorted array

//solution:
//suppose there is the array a[n] with arithmetic progression:
// ... a[i], a[j], a[k], use A[i][j] to symbol the number of arithmetic progression
//starting from a[i], a[j], then A[i][j] = 1 + A[j][k], in which case
//a[j] - a[i] == a[k] - a[j]; since the array is sorted, from each possible
//middle point j, we can extend on left and right to seek out all pairs that make
//a[i] - a[left] == a[right] - a[i]

const int M = 15;
int GetLPS(int a[M])
{
	assert(a);
	if (1 == M) return 1;

	int rec[M][M];
	for (int i =0; i < M; i++)
		for (int j = 0; j < M; j++)
			rec[i][j] = 2;

	int nMax = 2;
	for (int i = M - 2; i >= 1; i--)
	{
		int nLft = i - 1;
		int nRgt = i + 1;
		while (nLft >= 0 && nRgt < M)
		{
			if (a[i] - a[nLft] == a[nRgt] - a[i])
			{
				//one thing is if you iterate from left to right,
				//you should assign to rec[i][nRgt] rather than rec[nLft][i]
				rec[nLft][i] = rec[i][nRgt] + 1;
				if (rec[nLft][i] > nMax)
					nMax = rec[nLft][i];

				//well, the continuous same elements don't affect the result
				//why???
				nLft--, nRgt++; 
			}
			else if (a[i] - a[nLft] < a[nRgt] - a[i])
				nLft--;
			else nRgt++;
		}
	}

	return nMax;
}

设下标 j < i < k

f[i,k]表示以a[i], a[k]为等差数列的最后两项的最长长度

如果 a[i]-a[j] = a[k] - a[i]则 f[i,k] = f[j,i] +1

int maxDiffLen(int *a, int n) {
    vector<vector<int> > vt(n);
    for (int i = 0; i < n; ++i)
        vt[i].resize(n , 2 );

    int maxLen = 0;

    for (int i = 1; i < n - 1 ; ++i ) {
        int j = i - 1;
        int k = i + 1;

        while (j >= 0 && k < n) {
            if (a[k] - a[i] > a[i] - a[j]) --j;
            else if ( a[k] - a[i] < a[i] - a[j] ) ++k;
            else {
                vt[i][k] = vt[j][i] + 1;
                if (vt[i][k] > maxLen)
                    maxLen = vt[i][k];
                ++k;
                --j;
            }
        }
    } 
    
    return maxLen;
    

}

又想到一种方法，但是很占内存。f[i][k]表示以a[i]结尾的，差为k的数列的最大长度。

int getLArray(int *a, int n) {
    int maxDiff = a[n-1] - a[0];
    int ** f = new int *[n];
    for (int i = 0; i < n ; ++i)
        f[i] = new int [maxDiff+1];

    for (int i = 0; i < n ; ++i)
        for (int j = 0; j <= maxDiff; ++j)
            f[i][j] = 1;

    int maxLen = 2;
    for (int i = 1; i < n; ++i) {
        for (int j = i - 1; j >=0; --j) {
            int k = a[i] - a[j];
            if (f[i][k] < f[j][k] + 1)
                f[i][k] = f[j][k] + 1;
            if (maxLen < f[i][k])
                maxLen = f[i][k];
        }
    }

    for (int i = 0; i < n; ++i)
        delete [] f[i];
    delete []f;

    return maxLen;
}