using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace FindLongestAP
{
class APInfo
{
// stores the start index of the original data set for the AP found
internal int startIndex;
// stores the end index of the original data set for the AP found
internal int endIndex;
// stores the difference for the the AP found
internal int diff;
};

class Program
{
static void Main(string[] args)
{
int[] data = new int[] {2, 3, 5, 7, 8, 4, 9, 5, 10, 6};

APInfo apInfo = FindLongestAPInfo(data);

for (int i = apInfo.startIndex; i <= apInfo.endIndex; i++)
{
Console.Write("{0} ", data[i]);
}
}

///

/// The main idea is scanning the data set to find the complete AP, then compare the
/// current found AP with the longest one found so far, if the current one is longer,
/// then update the longest one with the current one. After finished scanning the whole
/// data set, then the longest AP is determined. O(N) complexity.
///

///
///
static APInfo FindLongestAPInfo(int[] data)
{
if (data == null || data.Length < 2)
{
return null;
}

// Initialize
APInfo currentAPInfo = new APInfo();
currentAPInfo.startIndex = 0;
currentAPInfo.endIndex = 1;
currentAPInfo.diff = data[1] - data[0];

APInfo longestAPInfo = new APInfo();
longestAPInfo.startIndex = 0;
longestAPInfo.endIndex = 1;
longestAPInfo.diff = data[1] - data[0];

for (int i = 2; i longestAPInfo.endIndex - longestAPInfo.startIndex)
{
longestAPInfo.startIndex = currentAPInfo.startIndex;
longestAPInfo.endIndex = currentAPInfo.endIndex;
}
// update currentAPInfo to start a new one
currentAPInfo.startIndex = i - 1;
currentAPInfo.endIndex = i;
currentAPInfo.diff = diff;
}
}

return longestAPInfo;
}
}
}

Advertisements