可爱静

记录生活、学习和工作

0%

最大子序和_力扣53

发表于 更新于 分类于
本文字数： 544 阅读时长 ≈ 1 分钟

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

思路及算法

运用动态规划的思路解决

  • 动态规划的是首先对数组进行遍历，当前最大连续子序列和为 sum，结果为 res
  • 如果 sum > 0，则说明 sum 对结果有增益效果，则 sum 保留并加上当前遍历数字
  • 如果 sum <= 0，则说明 sum 对结果无增益效果，需要舍弃，则 sum 直接更新为当前遍历数字
  • 每次比较 sum 和 res 的大小，将最大值置为 res，遍历结束返回结果
  • 时间复杂度：O(n)O(n)

    实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    class Solution {
        public int maxSubArray(int[] nums) {
            int res = nums[0];
            int sum = 0;
            for (int num : nums) {
    	// 判断是否有增益效果
               if (sum > 0){
                   sum += num;
               }else {
    	// 没有增益效果，将sum赋值为当前遍历数
                   sum = num;
               } 
    	// 在res和sum中选取最大值赋值给res
               res = Math.max(res, sum);
            }
            return res;
        }
    }

来源：力扣（LeetCode）