53.最大子序和.md

53. 最大子序和

https://leetcode-cn.com/problems/maximum-subarray/

Java

/*
 * @Author: Goog Tech
 * @Date: 2020-09-15 13:44:15
 * @LastEditTime: 2020-09-15 13:44:36
 * @Description: https://leetcode-cn.com/problems/maximum-subarray/
 * @FilePath: \leetcode-googtech\#53. Maximum Subarray\Solution.java
 * @WebSite: https://algorithm.show/
 */

class Solution {
    // DP : 动态规划,解题思路如下所示:
    // 1. 首先对数组进行遍历,设当前最大连续子序列和为 sum, 结果为 result
    // 2. 若 sum > 0,则说明 sum 对结果有增益效果,进而将当前所遍历的数字累加到 sum
    // 3. 若 sum <= 0,则说明 sum 对结果无增益效果,进而舍弃当前所遍历数字,并将 sum 更新为当前所遍历的数字
    // 4. 每次比较 sum 与 result 的大小,即将最大值置为 result,遍历结束后返回结果即可
    public int maxSubArray(int[] nums) {
        int result = nums[0], sum = 0;
        for(int num : nums) {
            if(sum > 0) sum += num;
            else sum = num;
            result = Math.max(result, sum);
        }
        return result;
    }
}

Python

'''
Author: Goog Tech
Date: 2020-09-15 13:44:20
LastEditTime: 2020-09-15 13:44:46
Description: https://leetcode-cn.com/problems/maximum-subarray/
FilePath: \leetcode-googtech\#53. Maximum Subarray\Solution.py
WebSite: https://algorithm.show/
'''

class Solution(object):
    # DP : 动态规划
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        for i in range(1, len(nums)):
            if nums[i - 1] > 0: 
                nums[i] += nums[i - 1]
        return max(nums)