【Leetcode】53.最大子序和

53 最大子序和

题目：
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

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

思路：

方法：用动态规划求解。
用函数f(i)表示以第i个数字结尾的子数组的最大和。
题目要求的是max[f(i)]
若i=0或f(i-1)<=0,则f(i) = pData[i].
若i!=0并且f(i-1) > 0, 则f(i) = pData[i] + f(i-1)

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int maxSubArray(int[] nums) {
        int maxSum = nums[0];
        //pre表示以第i-1个数字结尾的子数组的最大和。将其初始化为nums[0]
        int pre = nums[0];
        int cur;
        for(int i = 1;i < nums.length; i++){
            //如果pre小于0，则以第i个数字结尾的子数组的最大值cur就是这个数字本身，不带上pre。更新maxSum
            if(pre <= 0){
                cur = nums[i];
                maxSum = Math.max(maxSum, cur);
            }
            //如果pre大于0,则以第i个数字结尾的子数组的最大值cur为以第i-1个数字结尾的子数组的最大和pre加上当前位置值。
            else{
                cur = pre + nums[i];
                maxSum = Math.max(maxSum, cur);
            }
            //更新pre
            pre = cur;  
        }
        return maxSum;
    }
}