public int searchInsert(int[] nums, int target) {
    // 右邊界最大的數有可能就是答案(最衰的情況下)，他的index就是長度
    int len = nums.length, left = 0, right = len;
    // 開始迫近
    while (left < right) {
        // 每輪都重新定義中間數，注意小數點會被捨去
        int mid = left + (right - left) / 2;
        // 如果目標更大
        if (nums[mid] < target) {
            // 成為新的左標，下一輪搜尋[mid + 1...right]
            left = mid + 1; // 因為小數點會被捨去，所以這邊+1
        } else {
            // 成為新的右標，下一輪搜尋[left...mid]
            right = mid;
        }
        // 直到nums[mid] = target
    }
    return left;
}

public int maxSubArray(int[] nums) {
    /**
     * Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
     * Output: 6
     * Explanation: [4,-1,2,1] has the largest sum = 6.
     * 找出子數組(連續的)最大和
     */
    int n = nums.length;
    // 動態用來儲存最大值的數組，長度等於原數組，因為到時候要一個一個比過去
    int[] dp = new int[n];
    dp[0] = nums[0];
    // 先假設第一個數自己就是最大值
    int max = nums[0];
    // 從第二個數開始比對
    for (int i = 1; i < n; i++) {
        // 判斷"動態數組的前一個數"加"原數組當前數"，哪個更大，原數組更大就成為動態數組的新成員
        dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
        // 動態數組每輪更新的結果是累加的和，直到下一個數是負的才停
        // 更新最終要返回的max
        max = Math.max(max, dp[i]);
    }
    return max;
}

public int lengthOfLastWord(String s) {
    /**
     * Input: s = "Hello World"
     * Output: 5
     * Explanation: The last word is "World" with length 5.
     * 輸入sting可能包含空格，找出最後一個單字的長度
     */
    // 從尾遍歷
    int len = s.length();
    int end = len - 1;
    // 如果找到空格就停
    for (; end >= 0 && s.charAt(end) == ' '; end--) {
    }
    // 單字的長度，直到空格又停
    int wordLength = 0;
    for (; end >= 0 && s.charAt(end) != ' '; end--) {
        wordLength++;
    }
    return wordLength;

}