最大子数组和及其变种延申

53.最大子数组和

//dp
class Solution {
    public int maxSubArray(int[] nums) {
		int[] dp = new int[nums.length + 1];
		int res = Integer.MIN_VALUE;
		for(int i = 1; i <= nums.length; i++){
			dp[i] = Math.max(nums[i-1], dp[i-1] + nums[i-1]);
			res = Math.max(res, dp[i]);
		}
		return res;
	}
}

变种：输出最大子数组和的起始和结束节点

class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length + 1];
        int res = Integer.MIN_VALUE;
        int start = 0, end = 0;
        int final_s = 0, final_e = 0;
        // 主要是判断前面的dp[i-1]如果是正数，那么当前一定加上前面的数，end调整为i，
        //否则不需要前面的累加，start和end直接更新为当前i
        for (int i = 1; i <= nums.length; i++) {
            if (dp[i - 1] > 0) {
                dp[i] = dp[i - 1] + nums[i - 1];
                end = i - 1;
            }else {
                dp[i] = nums[i - 1];
                start = i - 1;
                end = i - 1;
            }
            if(dp[i] > res){
                res = dp[i];
                final_s = start;
                final_e = end;
            }
        }
        System.out.println("最大子数组开始位置为：" + final_s + " 结束位置为：" + final_e);
        return res;
    }
}

变种：返回其大于等于target的最短的子数组的长度
剑指Offer Ⅱ 008

class Solution {
	// 滑动窗口
    public int minSubArrayLen(int target, int[] nums) {
		int left = 0, total = 0, res = nums.length + 1;
		for(int right = 0; right < nums.length; right++){
			total += nums[right];
			while(left <= right && total >= target){
				res = Math.min(res, right - left + 1);
				total -= nums[left];
				left++;
			}
		}
		return res = res == nums.length + 1 ? 0: res;
    }
}

// 若需要输出开始结束位置
class Solution {
	// 滑动窗口
    public int minSubArrayLen(int s, int[] nums) {
		int left = 0, total = 0, res = nums.length + 1;
        int start = 0, end = 0;
		for(int right = 0; right < nums.length; right++){
			total += nums[right];
			while(left <= right && total >= s){
                if(right - left + 1 < res){
                    start = left;
                    end = right;
                    res = right - left + 1;
                }
				total -= nums[left];
				left++;
			}
		}
        System.out.print("开始：" + start + " 结束：" + end);
		return res = res == nums.length + 1 ? 0: res;
    }
}

扩展到二叉树上，求二叉树最大路径和
124.二叉树中的最大路径和

class Solution {
    int res;
    public int maxPathSum(TreeNode root) {
        res = Integer.MIN_VALUE;
        dfs(root);
        return res;
    }
    private int dfs(TreeNode root){
        if(root == null) return 0;
        int left = dfs(root.left);
        int right = dfs(root.right);
        int in = root.val + left + right;
        res = Math.max(res, in);
        int out = root.val + Math.max(Math.max(left, right), 0);
        return out > 0 ? out: 0; 
    }
}