最大子序列和

 

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

示例:

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/maximum-subarray

题解:解决该题可用动态规划的算法,每次比较当前值和子序列的值谁最大,然后再将得到的最大值和历史最大值进行比较后可得到最大值。

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        max_num = curr_num = nums[0]
        for i in range(1, n):
            curr_num = nums[i] if nums[i] > nums[i] + curr_num else nums[i] + curr_num
            max_num = max_num if max_num > curr_num else curr_num
        return max_num
点赞

发表评论

Title - Artist
0:00