[LeetCode 笔记] 53. Maximum Subarray

前言

　　这题是一个经典的动态规划问题，目标是找到一个阵列中连续子阵列的合还有回传最大值，时间複杂度可达 O(n)，这里有 JAVA 和 Python 的写法。

题目

Given an integer array nums, find the subarray with the largest sum, and return its sum.

给定一个整数阵列 nums ，找到最大总合的子阵列，然后回传子阵列的总合。

题目连结：https://leetcode.com/problems/maximum-subarray/

题目限制

1 <= nums.length <= 105
104 <= nums[i] <= 104

範例

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

Input: nums = [1]Output: 1Explanation: The subarray [1] has the largest sum 1.

Input: nums = [5,4,-1,7,8]Output: 23Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

思路&笔记

直观的做法是把元素依依累加下去，这也代表为连续的子阵列，然后再将这个子阵列相加的最大数存起来。

遍历索引累加下去，子阵列的合会越来越大，代表此子阵列的合上限一直在增加。(这样可以确保当前子阵列的总合是连续的，且是最大的值)再来比较子阵列的合跟最大值，更新到最大的值。后续要判断相加的合如果小于 0 的话，重新找子阵列的起点，再依依累加下去。因为子阵列的合为负数，表示对后续的合没有贡献，将其重置为 0。(假如是负数的话对于子阵列的合会被扣掉)

JAVA 实现

class Solution {    public int maxSubArray(int[] nums) {        int n = nums.length; // 阵列的长度        int max = Integer.MIN_VALUE; // 确保整数为最小值 (有可能比0还要小)        int sum = 0; // 子阵列的合                for(int i=0;i<n;i++){            sum += nums[i]; // 子阵列的合 + 当下索引的值            max = Math.max(sum,max); // 子阵列的合、最大值，取比较大的数                        if(sum<0) {                sum = 0; // 子阵列的合重製为 0            }        }                return max; // 回传最大值    }}

Python 实现

使用了和 Java 一样的逻辑执行，换成 Python 的写法。

class Solution:    def maxSubArray(self, nums: List[int]) -> int:                n = len(nums) # 阵列长度        current_sum = 0 # 子阵列的合        current_max = float('-inf') # 确保是最小的整数        for i in range(n):            current_sum += nums[i] # 子阵列的合 + 当下索引的值            current_max = max(current_sum, current_max) # 子阵列的合、最大值，取比较大的数            if (current_sum<0):                  current_sum = 0 # 子阵列的合重製为 0                return current_max # 回传最大数

成绩

(新手上路，如有错误请友善告知，感谢)

Blog
https://chris81051.github.io/2023/05/31/LeetCode-53-Maximum-Subarray-Java-Python/
有分享技术文章、科技新闻、日常生活，欢迎一起讨论