算法 2.3.2 最大子序和【leetcode 53】

题目描述

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

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

进阶:
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

数据结构

• 数组

算法思维

• 遍历、贪心
  
  

解题思路

一. Comprehend 理解题意

• 找出一个子数组，使所有元素的和最大
  
  

二. Choose 选择数据结构与算法

贪心算法（动态规划）

• 数据结构：数组
• 算法思维：遍历、贪心、动态规划
• 解题思路
  1）累加当前元素之前，先判断当前累加和的正负
  2）如果为正，则当前元素 + 当前累加 > 当前元素，当前累加和对后续累加和起正面作用，参与累加
  3）如果为负，则当前元素 + 当前累加 < 当前元素，当前累加和对后续累加和起负面作用，舍弃，不参与累加
  4）判断每次得到的新累加和是否超过了最大值，超过则成为新的最大值
  5）返回最大值
  
  

三. Code 编码实现基本解法

class Solution {
   public int maxSubArray(int[] nums) {

        int max = nums[0]; //当前最大值
        int sum = 0; //当前累加值

        for (int num : nums){
            if (sum > 0) sum += num; //如果累加值为正，参与累加
            else sum = num; //如果累加值为负，不参与累加，当前值为新累加值
            max = Math.max(max,sum); //若新累加值大于最大值，代替最大值
        }

        return max; //返回最大值
    }
}

执行耗时：1 ms，击败了 93.43% 的Java用户
内存消耗：38.5 MB，击败了 42.23% 的Java用户

时间复杂度：O(n)
  • 原数组遍历 O(n)

空间复杂度：O(1)
  • 两个整型变量，常数级内存空间 O(1)

四. Consider 思考更优解

=== 待续 ===

五. Code 编码实现最优解

=== 待续 ===

六. Change 变形与延伸

=== 待续 ===