/********************************************************************

    purpose:    微软笔试题

    求随机数构成的数组中找到长度大于=3的最长的等差数列
    输出等差数列由小到大: 
    如果没有符合条件的就输出
    格式：
    输入[1,3,0,5,-1,6]
    输出[-1,1,3,5]
    要求时间复杂度，空间复杂度尽量小

 *********************************************************************/
#include <iostream>
#include <set>
#include <vector>

using namespace std;

// 归并排序
void Merge(int rOrg[], int rBuf[], int from, int mid, int to)
{
    int i = from;
    int j = mid + 1;
    int k = from;
    while (i <= mid && j <= to)
    {
        if (rOrg[i] <= rOrg[j])
            rBuf[k++] = rOrg[i++];
        else
            rBuf[k++] = rOrg[j++];
    }
    if (i <= mid)
        while (i <= mid)
            rBuf[k++] = rOrg[i++];
    else
        while (j <= to)
            rBuf[k++] = rOrg[j++];
    while(k>from)
        rOrg[--k] = rBuf[k];
}
// 归并排序
void MergeSort(int r[], int rBuf[], int from, int to)
{
    if (from == to)
        rBuf[from] = r[from];
    else
    {
        int mid = (from + to) / 2;
        MergeSort(r, rBuf, from, mid);
        MergeSort(r, rBuf, mid + 1, to);
        Merge(rBuf, r, from, mid, to);
    }
}
// 二分查找
int BinarySearch(int *r, const int &item, int left, int right)
{
    int middle;
    while(left <= right)
    {
        middle    = (left + right)/2;
        if(r[middle] == item)
            return    middle;
        else if(r[middle] < item)
            left = middle + 1;
        else
            right = middle - 1;
    }
    return -1;
}

// 求随机数构成的数组中找到长度大于=3的最长的等差数列
void MaxLenEQDistSubArray(int rOrg[], int len) {
    if (rOrg == NULL || len < 3) {
        return;
    }
    int *rBuf = new int[len]; // 用于归并排序
    MergeSort(rOrg, rBuf, 0, len-1);

    int** steps = new int*[len];
    int* stepP;
    int i, j, k, jEnd, left, right=len-1,
        curDist, curLastItem, curLen=0,
        maxDist, maxLastItem, maxLen=2;

    // 初始化 步数数组
    for (i = 0; i < len; i++) {
        steps[i] = new int[len-i];
        stepP = steps[i];
        for (int j = len-i-1; j >= 0; j-- ) {
            stepP[j] = 0;
        }
    }

    // 开始查找最大等差子数组
    // i为等差第一项的位置 j为等差第二项位置
    for (i = 0; i < len; i++) {
        jEnd = len - 1; // 要求的等差数列最小长度为3，等差第二项最大为原数组倒数第二项
        stepP = steps[i];
        for (j = i + 1; j < jEnd; j++) {
            if (stepP[j-i-1]) { // ① 此index步长j-i己被前面②计算过
                continue;
            }
            //stepP[j-i-1]=1; // 可省略，因为不会再访问这个标志
            curLastItem = rOrg[j];
            curDist = rOrg[j]-rOrg[i]; // 本次等差
            left = j;
            curLen = 2;
            while ((k=BinarySearch(rOrg, curLastItem+curDist, left+1, right)) != -1) { //是否存在下一等差数
                curLen++;
                curLastItem += curDist;
                steps[left][k-left-1] = 1; // ② 记录 index为left位置 index步长k-left 的数组己被前面计算过
                left = k;
            }
            if (curLen > maxLen) { // 记录最大等差数列信息
                maxLen = curLen;
                maxLastItem = curLastItem;
                maxDist = curDist;
            }
            
        }
    }

    // 输出结果
    if (maxLen >= 3) {
        int start = maxLastItem - maxDist*(maxLen-1);
        cout<<"max length:"<<maxLen<<endl;
        cout<<"max sub array: ";
        while(maxLen--)
        {
            cout<<start<<" ";
            start += maxDist;
        }
        cout<<endl;
    } else {
        cout<<"no GT 3 length sub array"<<endl;
    }

    delete[] rBuf;
    delete[] steps;
}

void Test_MaxLenEQDistSubArray()
{
    //// test MergeSort
    //const int LEN = 8;
    //int rOrg[LEN]={10,3,5,1,9,34,54,565},rBuf[LEN];
    //MergeSort(rOrg, rBuf, 0, LEN-1);
    //for (int i = 0; i < LEN; i++)
    //    cout << " " << rOrg[i];

    int rOrg[] = {1,3,0,5,-1,6}; //{1,3,0,5,-1,6}; {1,3,7,8,9,10,11,0,5,-1,6}; {1,3,7,8,9,10,11,12,0,5,-1,6}; {1,3,7,8,9,10,11,12,13,0,5,-1,6};
    MaxLenEQDistSubArray(rOrg, sizeof(rOrg)/sizeof(rOrg[0]));

    {
        int rOrg[] = {1,3,7,8,9,10,11,0,5,-1,6}; 
        MaxLenEQDistSubArray(rOrg, sizeof(rOrg)/sizeof(rOrg[0]));
    }
    {
        int rOrg[] = {1,3,7,8,9,10,11,12,0,5,-1,6}; 
        MaxLenEQDistSubArray(rOrg, sizeof(rOrg)/sizeof(rOrg[0]));
    }
    {
        int rOrg[] = {1,3,7,8,9,10,11,12,13,0,5,-1,6}; 
        MaxLenEQDistSubArray(rOrg, sizeof(rOrg)/sizeof(rOrg[0]));
    }

}