Mean:
給你一個字元串，每個字元都有一個權值(可能為負)，你需要将這個字元串分成兩個子串，使得這兩個子串的價值之和最大。一個子串價值的計算方法：如果這個子串是回文串，那麼價值就是這個子串所有字元權值之和；否則價值為0。
analyse:
擴充KMP算法運用。
總體思路：
找出所有包含第一個字母的回文串和包含最後一個字母的回文串，然後O(n)掃一遍，每次判斷第i個字母之前（包含第i個字母）的子串是否是回文，以及從第i個字母後的子串是否是回文，然後計算出答案，取最大值。
具體做法：
假設輸入的字元串是"abcda"
構造串s1="abcda#adcba"
求s1的Next數組，得到了包含第一個字母的回文串的位置；
構造串s2="adcba#abcda"
求s2的Next數組，得到了包含最後一個字母的回文串的位置；
用兩個flag數組标記這些位置，然後掃一遍就得答案了。
中間加一個'#'并後接反串的目的是：當整個串都是回文的時候能夠被Next數組記錄下。
Time complexity: O(nlogn)
Source code:
第一遍寫，不夠優化：
View Code
優化後的代碼：