LeetCode53 最大子序和

目录

题目

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

思路

动态规划

假设 nums 数组的长度是 n，下标从 0 到 n-1

用 f(i)代表以 num[i] 结尾的连续子数组的最大和

我们要求的就是 f(0)~f(n-1)中的最大值

而 f(i) = max{ f(i-1)+num[i] , num[i] }

class Solution {
    public int maxSubArray(int[] nums) {
        int maxSum = nums[0];
        int pre = 0;
        for(int x : nums){
            pre = Math.max(pre + x, x);
            maxSum = Math.max(maxSum, pre);
        }
        return maxSum;
    }
}

时间复杂度：O(n)

空间复杂度：O(1)