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

    purpose:    微軟筆試題

    求隨機(jī)數(shù)構(gòu)成的數(shù)組中找到長(zhǎng)度大于=3的最長(zhǎng)的等差數(shù)列
    輸出等差數(shù)列由小到大: 
    如果沒(méi)有符合條件的就輸出
    格式：
    輸入[1,3,0,5,-1,6]
    輸出[-1,1,3,5]
    要求時(shí)間復(fù)雜度，空間復(fù)雜度盡量小

 *********************************************************************/
#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;
}

// 求隨機(jī)數(shù)構(gòu)成的數(shù)組中找到長(zhǎng)度大于=3的最長(zhǎng)的等差數(shù)列
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;

    // 初始化 步數(shù)數(shù)組
    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;
        }
    }

    // 開(kāi)始查找最大等差子數(shù)組
    // i為等差第一項(xiàng)的位置 j為等差第二項(xiàng)位置
    for (i = 0; i < len; i++) {
        jEnd = len - 1; // 要求的等差數(shù)列最小長(zhǎng)度為3，等差第二項(xiàng)最大為原數(shù)組倒數(shù)第二項(xiàng)
        stepP = steps[i];
        for (j = i + 1; j < jEnd; j++) {
            if (stepP[j-i-1]) { // ① 此index步長(zhǎng)j-i己被前面②計(jì)算過(guò)
                continue;
            }
            //stepP[j-i-1]=1; // 可省略，因?yàn)椴粫?huì)再訪問(wèn)這個(gè)標(biāo)志
            curLastItem = rOrg[j];
            curDist = rOrg[j]-rOrg[i]; // 本次等差
            left = j;
            curLen = 2;
            while ((k=BinarySearch(rOrg, curLastItem+curDist, left+1, right)) != -1) { //是否存在下一等差數(shù)
                curLen++;
                curLastItem += curDist;
                steps[left][k-left-1] = 1; // ② 記錄 index為left位置 index步長(zhǎng)k-left 的數(shù)組己被前面計(jì)算過(guò)
                left = k;
            }
            if (curLen > maxLen) { // 記錄最大等差數(shù)列信息
                maxLen = curLen;
                maxLastItem = curLastItem;
                maxDist = curDist;
            }
            
        }
    }

    // 輸出結(jié)果
    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]));
    }

}