秦怀杂货店

General Store

  • 首页
  • 文章归档
  • 标签
  • 分类
  • 关于页面

  • 搜索
随便聊聊 数据结构 小游戏 数据库 Docker Springboot 系统设计 雪花算法 分布式 海量ip 最长回文子串 算法 面试题 线程池 多线程 线程 java学习 布隆过滤器 github 架构设计 docsify Git JVM LeetCode 杂货思考 设计模式 Lambda native isAssignableFrom 反射 剑指Offer mybatis SPI JDBC 编程工具 Java基础 集合

剑指Offer【30】-- 连续子数组的最大和

发表于 2020-12-26 | 分类于 剑指Offer | 0 | 阅读次数 266

题目描述

输入一个整型数组,数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为 O(n).

示例1

输入
[1,-2,3,10,-4,7,2,-5]

返回值
18

输入的数组为{1,-2,3,10,—4,7,2,一5},和最大的子数组为{3,10,一4,7,2},因此输出为该子数组的和 18。

第一种方法:暴力破解,使用两层循环,求每一个区间的和:

    public int simpleSolution(int[] array) {
        if (array == null || array.length == 0) {
            return 0;
        }
        int result = Integer.MIN_VALUE;
        for (int i = 0; i < array.length; i++) {
            int tempSum = 0;
            for (int j = i; j < array.length; j++) {
                tempSum = tempSum + array[j];
                if (tempSum > result) {
                    result = tempSum;
                }
            }
        }
        return result;
    }

使用动态规划求解,动态规划只要找出状态转移方程,就意味着成功了一大半。首先我们定义这个问题:
dp[i]表示下标以i结尾的连续子数组的最大和,假设数组大小为n,那么最终求解的就是dp[n-1]。

下标以i结尾的连续子数组的最大和,怎么求呢?要想求dp[i],那我们现在假设一下,假设下标以i-1结尾的连续子数组的最大和为dp[i-1],数组第i个元素是nums[i],那么当前的连续子数组的最大和,要么是前面的加上当前的元素:dp[i-1]+nums[i],要么是舍弃掉之前的dp[i-1](这个很可能是负数),取现在的nums[i];

因此,状态转移方程为:

dp[i]= Max{dp[i-1]+nums[i],nums[i]}

但是,值得注意的是,Max{dp[i-1]+nums[i],nums[i]}求得的仅仅是以i下标结尾的子数组的最大和,之前计算的连续子数组最大和需要保存起来,不断的和当前计算的最大和比较,取最大值。

    public int FindGreatestSumOfSubArray(int[] array) {
        int res = array[0]; //记录当前所有子数组的和的最大值
        int max = array[0];   //包含array[i]的连续数组最大值
        for (int i = 1; i < array.length; i++) {
            max = Math.max(max + array[i], array[i]);
            res = Math.max(max, res);
        }
        return res;
    }
  • 本文作者: 秦怀杂货店
  • 本文链接: http://aphysia.cn/archives/jianzhioffer30
  • 版权声明: 本博客所有文章除特别声明外,均采用CC BY-NC-SA 3.0 许可协议。转载请注明出处!
# 随便聊聊 # 数据结构 # 小游戏 # 数据库 # Docker # Springboot # 系统设计 # 雪花算法 # 分布式 # 海量ip # 最长回文子串 # 算法 # 面试题 # 线程池 # 多线程 # 线程 # java学习 # 布隆过滤器 # github # 架构设计 # docsify # Git # JVM # LeetCode # 杂货思考 # 设计模式 # Lambda # native # isAssignableFrom # 反射 # 剑指Offer # mybatis # SPI # JDBC # 编程工具 # Java基础 # 集合
杂货思考【1】-- 初衷与兴趣
剑指Offer【31】-- -- 整数中1出现的次数
  • 文章目录
  • 站点概览
秦怀杂货店

秦怀杂货店

纵然缓慢,驰而不息。

145 日志
19 分类
37 标签
Github E-mail
Creative Commons
0%
© 2022 秦怀杂货店
由 Halo 强力驱动
|
主题 - NexT.Pisces v5.1.4