解题思路：
- 状态定义： currentMax 表示以当前元素结尾的最大子数组和。globalMax 表示遍历过程中遇到的所有子数组的最大和。
- 状态转移： 对于每个元素 nums[i]，有两种选择：将其作为新子数组的起点，即 nums[i]；将其附加到前一个子数组末尾，即 currentMax + nums[i]。
- 初始化与更新： 初始时，currentMax 和 globalMax 均为数组第一个元素的值。遍历数组剩余元素，逐次更新 currentMax 和 globalMax。
Java代码：
class Solution {public int maxSubArray(int[] nums) {int currentMax = nums[0];int globalMax = nums[0];for (int i = 1; i < nums.length; i++) {currentMax = Math.max(nums[i], currentMax + nums[i]);globalMax = Math.max(globalMax, currentMax);}return globalMax;}
}
复杂度分析：
- 时间复杂度： O(n)，仅需遍历数组一次，每个元素进行常数时间的操作。
- 空间复杂度： O(1)，仅使用两个变量，无额外空间开销。
解题思路：
- 排序： 首先将区间按照起始点 start 进行升序排序。这一步是为了保证后续处理时，只需比较当前区间与前一个合并后的区间即可。
- 合并： 遍历排序后的区间，维护一个合并结果的列表 merged。如果当前区间的起始点 start 小于等于 merged 中最后一个区间的结束点 end，说明两个区间有重叠或相邻，合并它们。否则，将当前区间直接加入 merged 列表中。
Java代码：
public class Solution {public int[][] merge(int[][] intervals) {if (intervals == null) {return new int[0][0];}Arrays.sort(intervals, (a, b) -> a[0] - b[0]);List<int[]> merged = new ArrayList<>();merged.add(intervals[0]);for (int i = 1; i < intervals.length; i++) {int[] current = intervals[i];int[] last = merged.get(merged.size() - 1);if (current[0] <= last[1]) {last[1] = Math.max(last[1], current[1]);} else {merged.add(current);}}return merged.toArray(new int[merged.size()][]);}
}
复杂度分析：
-
时间复杂度： O(nlogn)，主要开销在排序步骤，时间复杂度为 O(nlogn)。合并的时间复杂度为 O(n)。
-
空间复杂度： 需要额外的空间存储合并后的结果，最坏情况下（无重叠区间）空间复杂度为 O(n)。