JZ30 連續子數組的最大和
（簡單）
題目
描述
輸入一個整型數組，數組裡有正數也有負數。數組中的一個或連續多個整數組成一個子數組。求所有子數組的和的最大值。要求時間複雜度為 O(n)。
示例
輸入：
[1,-2,3,10,-4,7,2,-5]
傳回值：
18
說明：
輸入的數組為{1,-2,3,10,—4,7,2,一5}，和最大的子數組為{3,10,一4,7,2}，是以輸出為該子數組的和 18。
思路
使用動态規劃求解問題，最重要的就是确定從前一個階段轉化到後一個階段之間的遞推關系， 遞推關系必須是從次小的問題開始到較大的問題之間的轉化，從這個角度來說，動态規劃往往可以用遞歸程式來實作，不過因為遞推可以充分利用前面儲存的子問題的解來減少重複計算，是以對于大規模問題來說，有遞歸不可比拟的優勢，這也是動态規劃算法的核心之處。
是以，此題已明确限定時間複雜度為 O(n)，是以我們需要的首要任務是找清楚遞推關系公式，同時，因為我們的時間複雜度隻允許我們周遊一次數組，是以還需要用一個變量來記錄最大的子數組和，而且，由于該方法傳入的是引用型的數組變量，是以我們也要拷貝一份此數組，操作拷貝的那份，而不是直接操作傳入的那份，如果不這樣，那可能會在項目種産生十分嚴重的故障。而且我們也要考慮數組參數為 null 的情況，這時直接傳回和為 0 即可，使程式有較好的健壯性。
我們令拷貝的那份數組的名為 arr ，arr[i]（即數組中的第 i 個元素值） 的結果，根據 arr[i - 1] 推出，當 arr[i - 1] 為正數的時候，是可以促進待選子數組和變大的，是以要加上，即 arr[i] += arr[i - 1]，若 arr[i - 1] 為負數，則将使得待選子數組和變小，是以不應該加上，應舍棄 [0，i-1] 下标範圍内的數組元素，令 arr[i] += 0 即可，也就是從目前數組元素再次作為起始元素開始，并在每次進行上述求 arr[i] 的操作之後，用一個變量 max 來記錄下 arr[i] 的最大值即可，這樣就可以巧妙高效地選取出，最後變量 max 就正是和最大的子數組元素值的和。
實作
public class JZ30連續子數組的最大和 {
public int FindGreatestSumOfSubArray(int[] array) {
if (array == null) {
return 0;
}
int[] arr = new int[array.length];
System.arraycopy(array, 0, arr, 0, arr.length);
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
arr[i] += arr[i - 1] > 0 ? arr[i - 1] : 0;
max = Math.max(max, arr[i]);
}
return max;
}
} 
JZ4 重建二叉樹
（中等）
題目
描述 給定某二叉樹的前序周遊和中序周遊，請重建出該二叉樹并傳回它的頭結點。 例如輸入前序周遊序列{1,2,4,7,3,5,6,8}和中序周遊序列{4,7,2,1,5,3,8,6}，則重建出如下圖所示。提示: 1.0 <= pre.length <= 2000 2.vin.length == pre.length 3.-10000 <= pre[i], vin[i] <= 10000 4.pre 和 vin 均無重複元素 5.vin出現的元素均出現在 pre裡
【算法】解題總結：劍指Offer 30 連續子數組的最大和、劍指Offer 4 重建二叉樹 6.隻需要傳回根結點，系統會自動輸出整顆樹做答案對比
示例1
輸入：
[1,2,4,7,3,5,6,8],[4,7,2,1,5,3,8,6]
傳回值：
{1,2,3,4,#,5,6,#,7,#,#,8}
說明：
傳回根節點，系統會輸出整顆二叉樹對比結果
示例2
輸入：
[1],[1]
傳回值：
{1}
示例3
輸入：
[1,2,3,4,5,6,7],[3,2,4,1,6,5,7]
傳回值：
{1,2,5,3,4,6,7}
思路
這次就偷個懶吧，隻想寫個代碼實作，但不想自己再寫思路了，碰巧有位大佬寫的思路也非常清晰易懂，我對此題也沒想到更巧妙的方法。
（下圖來源）
實作
public class JZ4重建二叉樹 {
public TreeNode reConstructBinaryTree(int[] pre,int[] in) {
if (pre == null || in == null
|| pre.length == 0 || in.length == 0) {
return null;
}
TreeNode root = new TreeNode(pre[0]);
for (int i = 0; i < in.length; i++) {
if (in[i] == pre[0]) {
root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(in, 0, i));
root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length), Arrays.copyOfRange(in, i + 1, in.length));
break;
}
}
return root;
}
}