題目：最大子數組和

原題鏈接：最大子數組和

方法1 動態規劃

public class T53 {//動態規劃public static int maxSubArray(int[] nums) {if (nums.length == 0) return 0;int[] dp = new int[nums.length]; // dp[i] 表示以 nums[i] 結尾的最大子數組和dp[0] = nums[0]; // 初始化狀態int res = dp[0]; // 初始化最大子數組和// 動態規劃狀態轉移for (int i = 1; i < nums.length; i++) {dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);  //狀態轉移方程res = Math.max(res, dp[i]);}return res;}public static void main(String[] args) {int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};System.out.println(maxSubArray(nums)); // 輸出: 6}
}

方法2

方法二可能不容易想到

public class T53 {public int maxSubArray(int[] nums) {// 初始化為int類型最小值int res = nums[0];int tempTotal = 0;for (int i = 0; i < nums.length; i++) {tempTotal += nums[i];// 記錄最大數值res = Math.max(tempTotal, res);if (tempTotal < 0) {// 如果和小于0,就重置為0，因為任何數加上一個負數一定小于當前數值tempTotal = 0;  //0加任何數都等于任何數}}return res;}public static void main(String[] args) {int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};System.out.println(maxSubArray(nums)); // 輸出: 6}
}

---

題目：合并區間

原題鏈接：合并區間

題解

    public static int[][] merge(int[][] intervals) {if (intervals.length == 0) {return new int[0][2];}// 可使用Lambda表達式Arrays.sort(intervals, new Comparator<int[]>() {@Overridepublic int compare(int[] interval1, int[] interval2) {return interval1[0]-interval2[0];}});List<int[]> merged = new ArrayList<>();for (int[] interval : intervals) {int L = interval[0], R = interval[1];// 如果merged列表為空，或者當前區間與上一個區間不重疊，直接添加當前區間if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < L) {merged.add(new int[]{L, R});} else {// 否則更新上一個區間的右邊界merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);}}//List.toArray(T[] a) 方法將列表中的所有元素存儲到指定類型的數組中return merged.toArray(new int[merged.size()][]);}

核心:
如果新區間的起始值大于 merged 列表中最后一個區間的結束值，則直接將新的區間添加到 merged 列表中；否則，更新 merged 列表中最后一個區間的結束值。

• 排序區間: 確保區間按照起始值從小到大排列，方便后續合并操作。
• 遍歷和合并: 遍歷排序后的區間數組，使用一個 merged 列表來存儲合并后的區間。如果當前區間與前一個區間不重疊，直接添加到 merged 列表；如果重疊，更新 merged 列表中最后一個區間的結束值。

---

?覺得有用的可以留個關注~~?