1、最大子序和 -53
题目
本来在力扣中找的是分治分类的题目，但是看了下面的进阶，就先尝试用循环的方式解一下，很明显O(n)的复杂度就是遍历一次数组。我的思路是数组从头遍历，第一个正数的地方开始加，后面的负数直接加上，如果到达下一个正数就判断前面的和，为正的话继续加和，为负就是隔开了，重新开始加和。还有就是在每个正数那里的和sum跟最大值比较一下，比max大的话，直接替换max。但是我忽略了序列中都是负数的情况，这样的话就是从中选一个最大的负数，所以我把max初始化为第一个元素。
提交结果
class Solution {
public int maxSubArray(int[] nums) {
int max = nums[0];
int sum = 0;
for(int i = 0; i < nums.length; i++) {
if(nums[i] > 0) {
if(sum <= 0) {
sum = nums[i];
} else {
sum += nums[i];
}
if(sum > max) {
max = sum;
}
} else {
if(nums[i] > max) {
max = nums[i];
}
sum += nums[i];
}
}
return max;
}
}
既然是分治的题目，当然还能用递归来代替循环：一般使用分治算法思想来解决问题的时候，都是使用二叉树，将原问题拆分为两个子问题，直到只剩下一个元素没得选择，编程的时候难就难在如何将子问题进行合并。
这道题中分为三种情况：一是问题的最优解在左子区间，二是在右子区间，三是横跨左右区间。所以分治的时候往左右区间传递，合并的时候，要计算出整个区间的最优解，需要从中间向左右两边计算最大值加和。
提交结果
class Solution {
public int maxSubArray(int[] nums) {
return maxSubArrayHelper(nums, 0, nums.length - 1);
}
private static int maxSubArrayHelper(int[] nums, int low, int high) {
if(low == high) {
return nums[low];
}
int mid = low + (high - low) / 2;
int left = maxSubArrayHelper(nums, low, mid);
int right = maxSubArrayHelper(nums, mid + 1, high);
int cross = getCross(nums, low, high);
int result = Math.max(left, right);
result = Math.max(result, cross);
return result;
}
private static int getCross(int[] nums, int low, int high) {
int mid = low + (high - low) / 2;
int left = Integer.MIN_VALUE;
int sum = 0;
for(int i = mid; i >= low; i--) {
sum += nums[i];
left = Math.max(sum, left);
}
int right = Integer.MIN_VALUE;
sum = 0;
for(int i = mid + 1; i <= high; i++) {
sum += nums[i];
right = Math.max(sum, right);
}
return (left + right);
}
}
-
时间复杂度：
O(NlogN) - 空间复杂度：二叉树递归使用到栈，所以是O(logN)。
