5

Leetcode 053 最大子序和 ( Maximum Subarray ) 题解分析

 2 years ago
source link: https://nicksxs.me/2021/11/28/Leetcode-053-%E6%9C%80%E5%A4%A7%E5%AD%90%E5%BA%8F%E5%92%8C-Maximum-Subarray-%E9%A2%98%E8%A7%A3%E5%88%86%E6%9E%90/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

Leetcode 053 最大子序和 ( Maximum Subarray ) 题解分析

发表于 2021-11-28 分类于 Java ， leetcode 阅读次数： 14 阅读次数： 18 Disqus： 0 Comments

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Example 2:

Input: nums = [1]
Output: 1

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23

说起来这个题其实非常有渊源，大学数据结构的第一个题就是这个，而最佳的算法就是传说中的 online 算法，就是遍历一次就完了，最基本的做法就是记下来所有的连续子数组，然后求出最大的那个。

public int maxSubArray(int[] nums) {
        int max = nums[0];
        int sum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            // 这里最重要的就是这一行了，其实就是如果前面的 sum 是小于 0 的，那么就不需要前面的 sum，反正加上了还不如不加大
            sum = Math.max(nums[i], sum + nums[i]);
            // max 是用来承载最大值的
            max = Math.max(max, sum);
        }
        return max;
    }

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK