萤火小屋

优律的知识库

  • 首页
  • 归档
  • 分类
  • 标签
  • 留言
  • 关于

  • 搜索
双指针 力扣 动态代理 Git YAML SpringBoot SpringMVC 回溯算法 分治算法 归并排序 快排 手撕 事务 MySQL索引 MySQL 小技巧 Spring Framework Spring 动态规划 Linux Android 贪心算法 操作系统 进程调度模拟 IPv6 数据库 计算机组成原理 计算机基础 栈 Java 静态路由 路由器 交换机 数字通信 网络工程 计算机网络 Web http 大学学习技巧 程序设计 算法

力扣53题-最大子序和-动态规划题解

发表于 2021-04-21 | 分类于 力扣刷题 | 0 | 阅读次数 150

题目描述

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

样例

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

  2. 示例 2:
    输入:nums = [1]
    输出:1

  3. 示例 3:
    输入:nums = [0]
    输出:0

  4. 示例 4:
    输入:nums = [-1]
    输出:-1

  5. 示例 5:
    输入:nums = [-100000]
    输出:-100000
     

  • 提示:
    1 <= nums.length <= 3 * 104
    -105 <= nums[i] <= 105

题目评估

知识点:动态规划、数组、分治算法(我目前还没看这个算法在本题中的应用)
难度:简单(今天写写简单的吧~唉~)

分析

这题我以前做过,但是没有写博客记录总结知识点,现在补上。

确定状态:
本题状态为0..i长度的数组中的最大子数组和。

转移方程:
设res为最终的结果,dp为当前状态。
则转移方程为:
dp = max( nums[i] , dp + nums[i] )
res = max( dp , res )

初始条件:
res的初值为数组的第一个数:nums[0]。
状态dp的初值为0。

计算顺序:
计算顺序为数组从前往后的顺序。

另外本题还可以使用分治算法来求解,我还没有仔细看这个解题方案,可以参考官方题解方法二

Java代码题解

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

        int max = nums[0];  // 最大值 结果
        int dp = 0;  // 状态

        for (int i = 0; i < nums.length; i++) {  // 一次遍历数组
            
            // 比较:状态加上当前位置的数组值 和 当前位置的数组值 哪个大就取哪个赋给状态
            dp = Math.max(nums[i], dp + nums[i]);  

            // 比较:状态和当前记录的结果 哪个大就赋给结果
            max = Math.max(max , dp);

        }

        return max;
    }
}
力扣53题

复杂度分析

本题一遍遍历数组所以时间复杂度为O(n)。
状态保存为一个变量,所以空间复杂度为O(1)。

# 算法 # 程序设计 # 动态规划
力扣10题-正则表达式匹配
Java的集合类(容器)
  • 文章目录
  • 站点概览
优律

优律

优律的知识库

67 日志
17 分类
41 标签
E-mail Twitter Instagram
Links
  • CZLisyx - 浮生志
  • Vedfolnir
0%
© 2019 — 2022 萤火小屋——优律的博客网站
网站已勉强运行 
Halo博客系统技术支持