最大子序和(LeetCode-53)

简介: 最大子序和(LeetCode-53)

最大子序和(LeetCode-53)


题目

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


子数组 是数组中的一个连续部分。


示例 1:

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


示例 2:

输入:nums = [1]
输出:1


示例 3:

输入:nums = [5,4,-1,7,8]
输出:23


提示:


1 <= nums.length <= 105

-104 <= nums[i] <= 104

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


思路

五部曲


dp[i] 含义


包含下标 i ii 的最大连续子数组和

递推公式


前面的最大和加上当前元素的值首先必须是正的才有积极意义,其次如果小于当前元素值,那么当前元素就没有必要带前面的一起,不如自己当头元素

d p [ i ] = m a x ( d p [ i − 1 ] + n u m s [ i ] , n u m s [ i ] )

数组初始化


dp[0] 应该等于 n u m s [ 0 ]

遍历顺序


从前往后

测试用例


代码展示

class Solution
{
public:
    int maxSubArray(vector<int> &nums)
    {
        int n = nums.size();
        vector<int> dp(n);
        dp[0] = nums[0];
        int result = dp[0];
        for (int i = 1; i < n; i++)
        {
            dp[i] = max(dp[i - 1] + nums[i], nums[i]);
            result = max(result, dp[i]);
        }
        return result;
    }
};
目录
相关文章
|
虚拟化
vmware克隆虚拟机后没有ip地址的问题
解决vmware克隆虚拟机后没有内网ip的问题
|
安全 应用服务中间件 Linux
Linux上面配置Apache2支持Https(ssl)具体方案实现
虽然Nginx比较流行,但是由于一些老项目用到了Apache2来支持Web服务,最近想给服务上一个Https支持,虽然看似教程简单,但是也遇到一些特殊情况,经历了一番折腾也算是解决了所有问题,将过程记录如下。演示是基于Ubantu系统。
899 0
|
缓存 关系型数据库 PostgreSQL
PostgreSQL relcache在长连接应用中的内存霸占"坑"
除了常见的执行计划缓存、数据缓存,PostgreSQL为了提高生成执行计划的效率,还提供了catalog, relation等缓存机制。PostgreSQL 9.5支持的缓存如下 ll src/backend/utils/cache/ attoptcache.c catcache.c
7763 0
|
前端开发 API
基于若依的ruoyi-nbcio的flowable流程管理系统增加服务任务和我的抄送功能
基于若依的ruoyi-nbcio的flowable流程管理系统增加服务任务和我的抄送功能
396 0
|
存储 算法 前端开发
深入理解FFmpeg音视频编程:处理封装、解码、播放 队列与回放策略
深入理解FFmpeg音视频编程:处理封装、解码、播放 队列与回放策略
656 0
|
Ubuntu Linux 芯片
Linux(2)ubuntu rootfs根文件系统制作
Linux(2)ubuntu rootfs根文件系统制作
834 0
|
存储 Ubuntu Linux
linux系统中如何制作rootfs?详细教程
linux系统中如何制作rootfs?详细教程
394 0
|
存储 安全 测试技术
Golang Context 详细原理和使用技巧
Golang Context 详细原理和使用技巧
|
Java Linux
Linux下的JDK1.5安装
Linux下的JDK1.5安装
257 0