/*
 使用算法：動態規劃
 算法運行時間：O(n^3)

 題目補充點二：如果有一顆二叉樹形如圖1，那么它的中序遍歷為bac,前序遍歷為abc,后序遍歷為bca。
   a
  / \
 b   c
 (圖1)
 題目補充點三：輸入樣例所對應的二叉樹如圖2，請讀者寫出圖2的中序遍歷與前序遍歷，算出得分，并與題目對照是否正確，確保讀懂題意！
    3
  /   \
 1     4
  \     \
   2     5
 (圖2)
 題目補充點四：任何分數均不會出現負值。
 
     
     明確上面幾點后現在我們來考慮如何做這道題，首先要看到一點：題目給出的是中序遍歷，并且遍歷號為1、2、3、4、……、n，那么如果i是樹的根，則所有編號小于i的節點在樹中的位置均位于i的左邊，所有編號大于i的節點均位于i的右邊。
     根據這點我們來考慮更為一般性的定理。定理一：如果有一顆子樹，他的中序遍歷為a1、a2、a3、……、an（“a”后面的字符看成下標，如出現ai-1時，下標是i-1，表示第i-1個數，而不是第i個數減去1，下同），且子樹的根為ai，那么a1、a2、a3、……、ai-1均位于ai的左邊，ai+1、ai+2、……、an均位于ai的右邊。
 
 
     根據定理一，題目給出一個中序遍歷為1、2、3、……、n（這里的數字表示節點的編號，后面提到節點i及表示編號為i的節點）的二叉樹時我們可以任意假定某個節點i為樹的根而不會打亂二叉樹的中序遍歷，因為我們只要在二叉樹中把編號小于i的節點都放在i的左邊，編號大于i的節點都放在i的右邊即可，而湊巧的是，在中序遍歷序列中也有這一性質（及在中序遍歷序列中i左邊的數均小于i，i右邊的數均大于i），這為我們使用動態規劃方法來解此題提供了可能性。
     更進一步考慮，如果我們假設節點i為整個樹的根，那么節點1、2、3、……、i-1就組成了根節點的左子樹，同樣節點i+1、i+2、……、n組成了根節點的右子樹。此時我們又可以假設在左子樹中節點j（j<i）是左子樹的根，再次運用定理一可知，這種假設不會打亂整個樹的中序遍歷。同樣對于右子樹也成立。
 
     
     下面我們來考慮動態規劃的方法，我們暫時不考慮輸出前序遍歷的問題（關于動態規劃的更多信息請參考《算法導論》第15章）：
     考慮一：最優子結構。
     對于一顆中序遍歷為a1、a2、……、an的加分二叉樹，我們雖然不知道究竟哪個節點才是得分最大的二叉樹的根節點，但是我們可以每一個節點都試一下，看看那個節點作為根節點時能夠獲得的分數最大。比如當我們考慮把節點ai作為根節點，那么此時擺在我們面前的問題就是左、右子樹中的根又是哪個節點呢？答案是：左子樹的根節點是作為根時能夠讓左子樹得分最大的節點，右子樹的根節點是作為根時能夠讓右子樹得分最大的節點。請讀者自己證明！
     那么加分二叉樹的最優子結構可以表述如下：當選擇某節點為根時，如果要獲得最大的分數，那么根的左節點必使得左子樹能夠獲得最大分數，同樣根的右節點必使得右子樹能夠獲得最大分數。
 
 
     考慮二：重疊子問題。
     根據上面考慮的最優子結構性質，對于給出一個二叉樹的中敘遍歷求最大得分問題，我們需要考慮的僅有三個小問題，第一是如何選擇一個節點作為樹的根使得得分最大，第二是如何在左子樹中選擇一個節點作為左子樹的根使得左子樹的得分最大，第三個問題是如何在右子樹中選擇一個節點作為右子樹的根使得右子樹的得分最大。很明顯，問題二和問題三是問題一的重疊子問題。根據重疊性質可知，如果我們用函數MaxTreeScore(left,right)表示一個中序遍歷為left、left+1、left+2、……、right的二叉樹所能得到的最大加分，用變量nodeScore[i]表示編號為i的節點的分數，那么就有公式
     MaxTreeScore(left,right) = max{ MaxTreeScore(left,middle-1) * MaxTreeScore(middle+1,right) + nodeScore[middle] }，其中minddle從left遞增循環到right。這一點請讀者自己證明！
 
 
     考慮三：子問題獨立。
     根據上面的分析，子問題便是問題二和問題三，所謂子問題獨立就是說問題二的解決不會影響到問題三的解決，這一點顯然成立，請讀者自己證明！
 
     
     考慮四：做備忘錄。
     在程序運行中可能多次使用相同的參數調用MaxTreeScore函數，比如某時刻調用了MaxTreeScore(3,21)，另一時刻再次調用MaxTreeScore(3,21)，很明顯兩次調用得到的結果是相同的，因此可以用一個全局變量來保存這個值，當第一次調用時算出函數值保存起來，第二次調用時直接獲得此值而不用再次計算，這樣可以節約大量的時間！程序中我們用maxTreeScore[left][right]來保存MaxTreeScore(left,right)的值，注意，開頭為大寫字母的是函數，開頭為小寫字母的是變量，在我寫的代碼中均使用此規則！
 
 
     考慮五：邊界。
     MaxTreeScore函數會調用自己，但也不能每一次都調用自己，要不就會出現死循環調用，那么什么時候才是個頭呢？這就是邊界，跟據題意“葉子的加分就是葉節點本身的分數”可知當代如MaxTreeScore函數的兩個參數相等時就是求葉節點加分的情況，即MaxTreeScore(x,x)就為x節點的分數nodeScore[x]，根據題意“若某個子樹為空，規定其加分為1”可知，當代如MaxTreeScore函數的第一個參數大于第二個參數時此樹為空（不存在），即MaxTreeScore等于1。
 
 
     考慮六：所求。
     因為我們要求的是整個樹能夠得到的最大分數，根據上面的分析可知題目要求我們求出的最大分數即為MaxTreeScore(1,n)。注意，如果我們從0開始給節點編號的話所求就相應地為MaxTreeScore(0,n-1)，并且程序中就是這樣做的！
 
 
     最后，我們來考慮如何輸出一個分數獲得最大的二叉樹的前序遍歷，遍歷二叉樹需要知道些什么？遍歷二叉樹需要知道些什么？遍歷二叉樹需要知道些什么？請讀者先想一想！
 
     只要給我們任意一個子樹（包括整棵樹）的中序遍歷我們都知道這個子樹的跟節點是哪個的話，便可以前序遍歷整個二叉樹！（其實不僅是前序遍歷，中序遍歷、后序遍歷都行！這一點請讀者自己證明。）比如我們用Tree{left,right}表示中序遍歷為left、left+1、left+2、……、right的二叉樹,用root[left][right]保存這顆樹獲得最大分數時的根節點，那么對Tree{left,right}進行前序遍歷時及為先遍歷跟節點root[left][right]，然后遍歷左子樹Tree{left,root[left][right]-1}，最后遍歷右子樹Tree{root[left][right]+1,right}。這一點類似于上面考慮的重疊子問題。
     
     參考程序代碼如下
     
 */
 
 #include <cstdlib>
 #include "iostream"
 #include "fstream"
 
 using namespace std;
 const int max_n = 30;//最大節點數
 
 int n;//節點數，
 int nodeScore[max_n];//nodeScore[i]表示第i個節點的分數
 int maxTreeScore[max_n][max_n];//maxTreeScore[left][right]保存了由節點left、left+1、left+2、……、right構成的子樹能夠獲得的最大分數
 int root[max_n][max_n];//root[3][8]=5 表示由節點3、4、5、6、7、8構成的子樹在獲得最大分數時根節點為5
 
 //初始化全局變量，從輸入文件中讀取數據
 void init()//運行時間：O(n^2)
 {
     ifstream inputFile("tree.in");
     inputFile>>n;
     for(int i=0; i<n; i++)
         inputFile>>nodeScore[i];
     inputFile.close();
 
     for(int i=0; i<n; i++)
         for(int j=0; j<n; j++)
         {
             maxTreeScore[i][j] = -1;//初始化為-1，表示這個值為“未知”，因為分數不會出現負值所以此方法有效，否則需要設定一個特殊值表示“未知”
            root[i][j] = -1;//同樣用-1表示“未知”
        }
}

//MaxTreeScore(left,right)表示一個中序遍歷為left、left+1、left+2、……、right的二叉樹所能得到的最大加分
/**//*
    分析這個函數的運行時間，我們需要用到動態規劃時間分析工具，如下：
    考慮1：子問題數--questionCount
    所面對的問題不外乎求MaxTreeScore(i,j)的分數，那么總共要求多少次分數呢？
    及C(n,2)次，其中C(m,n)表示m個數中取n個的組合方案數，所以questionCount = O(n^2)
    考慮2：每個子問題所面臨的選擇數--chooseCount
    這里的選擇也就是對根的選擇，明顯對于長度為len的子樹有O(len)個選擇。所以chooseCount = O(n)
    因此運行MaxTreeScore(0,n-1)共需時間為：questionCount * chooseCount = O(n^3)
*/
int MaxTreeScore(int left, int right)//運行時間：O( (right - left) ^ 3 )
{
    //申明這顆樹能夠獲得的最大分數
    int score = -1;
    //申明這顆樹獲得最大分數時的根節點編號，使用后追“LR”是為了避免與全局變量重名
    int rootLR = -1;

    //如果這顆樹的最大分數已經算出
    if(maxTreeScore[left][right] != -1)
    {
        //則從保存最大分數的全局變量中獲取
        score = maxTreeScore[left][right];

        rootLR = root[left][right];
    }
    //如果否則這顆樹的最大分數還沒有算出，且這顆樹為空
    else if(left > right)
    {
        //那么分數為1
        score = 1;
    }
    //否則如果這顆樹的最大分數還沒有算出，且這顆樹是個葉節點
    else if(left == right)
    {
        //那么樹的分數為節點分數
        score = nodeScore[left];
        //根節點為葉節點自身
        rootLR = left;
    }
    //否則這顆樹的最大分數還沒有算出，且這顆樹必還有子結點
    else
    {
        //那么使用公式計算最大分數
        for(int i=left; i<=right; i++)
        {
            //如果i節點作為根節點能夠獲得更大的分數
            if(score < MaxTreeScore(left,i-1) * MaxTreeScore(i+1,right) + nodeScore[i] )
            {
                //更新最大分數
                score = MaxTreeScore(left,i-1) * MaxTreeScore(i+1,right) + nodeScore[i];
                //更新根節點為i
                rootLR = i;
            }
        }
    }

    //保存下這個最大分數避免再次計算
    maxTreeScore[left][right] = score;
    //保存下獲得最大分數時的根節點編號，以便輸出前序遍歷序列
    root[left][right] = rootLR;

    //返回最大分數
    return score;
}

//輸出子樹Tree{left,right}的前序遍歷
/**//*
    分析此函數的時間需要用到“分治法時間分析工具”，了解這個工具請參考我寫的其它文章,分析如下
    T(len) 表示len= right - left 時所需時間
    a = 2;
    b = 2;
    f(len) = O(1);
    考慮情況1，當s = 1(s>0)時，O(len^(log_b_a - s)=O(len^(log_2_2 - 1))=O(1)=f(len)
    得運行時間為：T(len) = O(len^(log_2_2)) = O(len)
*/
void ShowPreorderTraversal(int left, int right)//運行時間：O(right - left)
{
    //如果樹存在
    if(left <= right)
    {
        //先輸出根節點,別忘了我們是從0開始編號，所以輸出時要增加1
        cout<<root[left][right] + 1<<" ";
        //再輸出左子樹的前序遍歷
        ShowPreorderTraversal(left,root[left][right]-1);
        //最后輸出右子樹的前序遍歷
        ShowPreorderTraversal(root[left][right]+1,right);
    }
}

//輸出結果
void Show()//運行時間：O(n^3)
{
    //輸出最大分值
    cout<<MaxTreeScore(0,n-1)<<endl;//運行時間：O(n^3)

    //輸出整個樹的前序遍歷
    ShowPreorderTraversal(0,n-1);//運行時間：O(n)
}

int main(int argc, char *argv[])
{
    //初始化
    init();
    //顯示結果
    Show();
    system("PAUSE");
    return EXIT_SUCCESS;
}