Longest seq must either contain the smallest or not contain the smallest.
a) contains the smallest: use for loop to go thru the rest of the list as the second number, you will get the leap size. Try to use this leap size to test how long the seq can go.
b) doesn't contain the smallest number: use tail recursive to go thru the rest of the list.

Worst time complicity: O(n^3). Average should be close to O(n^2) because the inner loop will end when the first missing number is found.

it's not that hard as it looks like:

1) sort;
2) calculate delta different between current element & its immediate predecessor
3) count the longest sequence with the same delta.

code here:

1. sort
2.a create an ArrayList<ArrayList<Integer>> listOfSeries
2.b set maxLen = 0
3. Loop through the number list
for each number
3.1 Loop through the listOfSeries
for each series in the listOfSeries
If we can add the current number to the current series, add it. Set maxLen = +1
3.2 Add a new arrayList to the listOfSeries, this arrayList contains only the current number


Take {3,8,4,5,6,2,2} as example, then the final listOfSeries consists of:

,2,2
,2,3,4,5,6
,3,4,5,6
,4,5,6
,5,6
,6,8
,8

本文发表在 rolia.net 枫下论坛I used only basic language elements and it should straightforward to convert to Java or C or C++ or any similar language. I also appended the output of the code. I believe this is the optimal code: space O(N) and time O(N^3) Hope it helps

using System;
using System.Text;

namespace ArithmeticSeriesQuiz
{
....class Program
....{
........static void Main(string[] args)
........{
............Resolve(new int[] { 3, 8, 4, 5, 6, 2, 2 });
............Resolve(new int[] { -1, -5, 1, 3 });
............Resolve(new int[] { -10, -20, -10, -10 });
........}

........public static void Resolve(int[] values)
........{
............Console.WriteLine("Question series: {0}", ASeries.ArrayToString(values));
............int[] resultSeries;
............int length = ASeries.Longest(values, out resultSeries);
............Console.WriteLine("Returns: {0}", length);
............Console.WriteLine("Result series: {0}", ASeries.ArrayToString(resultSeries));
............Console.WriteLine();
........}
....}

....public class ASeries
....{
........public static int Longest(int[] values, out int[] longestSeries)
........{
............int lengthOfLongestSeries = 0;
............longestSeries = null;

............if (values != null && values.Length > 0)
............{
................// Sort
................for (int i = 0; i < values.Length; ++i)
................{
....................for (int j = i + 1; j < values.Length; ++j)
....................{
........................if (values[i] > values[j])
........................{
............................int temp = values[i];
............................values[i] = values[j];
............................values[j] = temp;
........................}
....................}
................}

................int[] workingSeries = new int[values.Length];

................for (int firstElementIndex = 0; firstElementIndex < values.Length; ++firstElementIndex)
................{
....................workingSeries[0] = values[firstElementIndex];

....................for (int secondElementIndex = firstElementIndex + 1; secondElementIndex < values.Length; ++secondElementIndex)
....................{
........................workingSeries[1] = values[secondElementIndex];
........................int lengthOfWorkingSeries = 2;

........................int delta = values[secondElementIndex] - values[firstElementIndex];
........................int nextElementValue = values[secondElementIndex] + delta;

........................for (int nextAvailableElementIndex = secondElementIndex + 1; nextAvailableElementIndex < values.Length; ++nextAvailableElementIndex)
........................{
............................if (values[nextAvailableElementIndex] > nextElementValue)
............................{
................................break; // next value of the arithmetic series is not in the array. this series can not be longer
............................}

............................if (values[nextAvailableElementIndex] == nextElementValue)
............................{
................................// found the next value of the arithmetic series, save it
................................workingSeries[lengthOfWorkingSeries++] = values[nextAvailableElementIndex];
................................nextElementValue = values[nextAvailableElementIndex] + delta;
............................}
........................}


........................if (lengthOfWorkingSeries > lengthOfLongestSeries)
........................{
............................lengthOfLongestSeries = lengthOfWorkingSeries;
............................longestSeries = new int[lengthOfLongestSeries];
............................for (int i = 0; i < lengthOfLongestSeries; ++i)
............................{
................................longestSeries[i] = workingSeries[i];
............................}
........................}

....................}
................}
............}

............return lengthOfLongestSeries;
........}

........public static string ArrayToString(int[] values)
........{
............StringBuilder buffer = new StringBuilder();
............buffer.Append("[ ");

............if (values != null && values.Length > 0)
............{
................for (int i = 0; i < values.Length; ++i)
................{
....................buffer.Append(values[i]);
....................buffer.Append(", ");
................}

................buffer.Length -= 2; // remove the last delimeter
............}
............buffer.Append(" ]");

............return buffer.ToString();
........}
....}
}



// Output
Question series: [ 3, 8, 4, 5, 6, 2, 2 ]
Returns: 5
Result series: [ 2, 3, 4, 5, 6 ]

Question series: [ -1, -5, 1, 3 ]
Returns: 3
Result series: [ -5, -1, 3 ]

Question series: [ -10, -20, -10, -10 ]
Returns: 3
Result series: [ -10, -10, -10 ]更多精彩文章及讨论，请光临枫下论坛 rolia.net

本文发表在 rolia.net 枫下论坛我从网上找的了这道题的思路。下面是我的java code


是从下面这个链接的思路里，改写的。
http://codercareer.blogspot.ca/2014/03/no-53-longest-arithmetic-sequence.html


import java.io.Console;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class ASeries {

public int longest(int[] values) {

// sort the array
Arrays.sort(values);

Map<Integer, List<Pair>> hashTable = buildHashTable(values);

return analyze(hashTable, values.length);
}

/*

for an array {3, 8, 4, 5, 6, 2, 2}, group the pars like this
differenece 0: (2,2)
difference 1: (2,3), (3,4), (4,5),(5,6)

so we need a hash table to store the information, the key is the difference.
the value is the indexes of the pairs(not values)
*/
private Map<Integer, List<Pair>> buildHashTable(int[] values) {

Map<Integer, List<Pair>> hashTable = new HashMap<Integer, List<Pair>>();

for (int i = 0; i < values.length; i++) {
for (int j = i + 1; j < values.length; j++) {

Pair pair = new Pair();
pair.setFirst(i);
pair.setSecond(j);

int diff = values[j] - values[i];
if (hashTable.containsKey(diff)) {
hashTable.get(diff).add(pair);
} else {
List<Pair> newValue = new ArrayList<Pair>();
newValue.add(pair);
hashTable.put(diff, newValue);
}
}
}

return hashTable;

}

/*
in this method, we need to get the length of the pairs with each difference.

A list of pairs with difference k is got given a key k in the hash table.
If an element A[i] is mth element is an arithmetic sequence with a common difference k, and there is a pair (A[i], A[j]) (j>i) in the list of pairs,
the element A[j] should be the m+1th elemement in the arithmetic sequence.

*/
private int analyze(Map<Integer, List<Pair>> hashTable, int lengthOfNumbers) {

int maxLength = 0;
for (int key : hashTable.keySet()) {
int[] lengths = new int[lengthOfNumbers];

for (int i = 0; i < lengthOfNumbers; i++) {
lengths[i] = 1;
}

for (Pair pair : hashTable.get(key)) {
lengths[pair.getSecond()] = lengths[pair.getFirst()] + 1;
}

for (int length : lengths) {
if (length > maxLength) {
maxLength = length;
}
}
}

return maxLength;
}

private static void test(String testName, int[] numbers, int expected) {

ASeries as = new ASeries();

if (as.longest(numbers) == expected) {
System.out.println(String.format("%s passed.", testName));
} else {
System.out.println(String.format("%s failed.", testName));
}
}

private static void test1() {
int[] numbers = {3, 8, 4, 5, 6, 2, 2};
int expected = 5;
test("test1", numbers, expected);
}

private static void test2() {
int[] numbers = {-1, -5, 1, 3};
int expected = 3;
test("test2", numbers, expected);
}

private static void test3() {
int[] numbers = {-10, -20, -10, -10};
int expected = 3;
test("test3", numbers, expected);
}

public static void main(String[] args) {
test1();
test2();
test3();
}

}

class Pair {
private int first;
private int second;

public int getFirst() {
return first;
}

public void setFirst(int first) {
this.first = first;
}

public int getSecond() {
return second;
}

public void setSecond(int second) {
this.second = second;
}
}


不知道哪里有这样的活动，让我们这些在多伦多的IT猥琐男，每月聚一下，大家交流，交流啊？哪位大侠有这样振臂一呼的能力？更多精彩文章及讨论，请光临枫下论坛 rolia.net

本文发表在 rolia.net 枫下论坛public class ASeries {
public static final int MIN_VALUES_LENGTH=2;
public static final int MAX_VALUES_LENGTH=50;
public static final int MIN_VALUE=-1000000;
public static final int MAX_VALUE=1000000;

public static void main(String[] args) throws Exception {
ASeries as=new ASeries();
System.out.println("res:"+as.longest(new int[] {3,8,4,5,6,2,2}));
}

public int longest(int[] values) throws Exception {
int ret=2;
if ( values == null || values.length < MIN_VALUES_LENGTH || values.length > MAX_VALUES_LENGTH ) {
throw(new Exception("values is null or has invalid amount of elements!"));
}
Arrays.sort(values);
if ( values[0] < MIN_VALUE || values[values.length-1] > MAX_VALUE ) {
throw(new Exception("At least one value is out of the range!"));
}
if ( values.length == 2 ) {
ret=2;
return ret;
}
int[] valuesDiff=new int[values.length-1];
for ( int i=1 ; i<values.length ; i++ ) {
valuesDiff[i-1]=values[i]-values[i-1];
}
int[] repeatCnt=new int[valuesDiff.length-1];
for ( int i=0 ; i<valuesDiff.length-1 ; i++ ) {
int tmpCount=1;
for ( int j=i+1 ; j<valuesDiff.length ; j++ ) {
if ( valuesDiff[j] == valuesDiff[i] ) {
tmpCount++;
}
}
repeatCnt[i]=tmpCount;
}
Arrays.sort(repeatCnt);
ret=repeatCnt[repeatCnt.length-1]+1;
return ret;
}

}更多精彩文章及讨论，请光临枫下论坛 rolia.net

先排序，然后用二分法， 给每一个部分里面数列最长到最短的进行排序。
然后是merge, merge中把左子集和右子集已有的相差距离数列相加然后再统计一下从最多到最少就不用说了，必须做的，最关键的是要把大于子数列距离的数距离都要统计一边，当然这些新出现的距离是“最少的”因为才出现了1次么，但这个是这里的关键，否则会漏掉有可能会成为最长数列的距离，这一步有O(k^2)。

二分法是O(nlogn),但是merge用了O(k^2), 所以有可能会变成 O(n2) O(n^2logn) O(n^3),我没算啊，错了别骂我。