最大子序和

发表于

算法：动态规划

​

题目

url：https://leetcode-cn.com/problems/maximum-subarray/

1
2
3
4
5
6
7
8
9
10
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

分析： 根据 最大和求最长子序列

长度为1的最大和子序列 => 长度为2的最大和子序列 => 长度为3的最大和子序列

​

Java解法

1、动态规划

求出每个位置（及其之前累计）的最大和：

max(i-1) >0 : max(i) = max(i-1) + nums[i]

max(i-1) <=0 : max(i) = nums[i]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class MaxKV {
    int i;
    int val;
    public MaxKV(int i, int val) {
    	this.i = i; this.val = val;
    }
}
class Solution {
    public int maxSubArray(int[] nums) {
        int maxVal=Integer.MIN_VALUE;
        MaxKV[] maxKV = new MaxKV[nums.length];
        for(int i=0; i<nums.length; ++i) {
            if(0==i) {
            	maxKV[i] = new MaxKV(i, nums[i]);
            } else {
                if(maxKV[i-1].val > 0) {
                	maxKV[i] = new MaxKV(maxKV[i-1].i, nums[i]+maxKV[i-1].val);
                } else {
                	maxKV[i] = new MaxKV(i, nums[i]);
                }
            }
            if(maxVal < maxKV[i].val) maxVal = maxKV[i].val;
        }
        return maxVal;
    }
}
public class App {
    public static void main(String[] args) {
        int[] nums = new int[] {-1};
//        int[] nums = new int[] {-2,1,-3,4,-1,2,1,-5,4};
        System.out.println(new Solution().maxSubArray(nums));
    }
}

​

2、分治法