LeetCode 面试题 16.17. 连续数列

这篇具有很好参考价值的文章主要介绍了LeetCode 面试题 16.17. 连续数列。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、题目

  给定一个整数数组,找出总和最大的连续数列,并返回总和。

示例:

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

进阶:

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

  点击此处跳转题目。

二、C# 题解

  使用动态规划可以实现 O(n) 的复杂度。使用 max 记录以 j 结尾的最大连续和,ans 记录从 0 ~ j 中的最大的连续数列和(不一定以 j 结尾),其递推关系为:

m a x [ j ] = M A X { m a x [ j − 1 ] + n u m s [ j ] , m a x [ j − 1 ] ≥ 0 n u m s [ j ] , m a x [ j − 1 ] < 0 a n s [ j ] = M A X { m a x [ j ] , c h o o s e   j a n s [ j − 1 ] , n o t   c h o o s e \begin{aligned} max[j]&= MAX\left\{ \begin{array}{l l} max[j-1]+nums[j],& max[j-1] \geq0\\ nums[j],& max[j-1]<0 \end{array} \right. \\\\ ans[j]&= MAX\left\{ \begin{array}{l l} max[j],& choose\ j\\ ans[j - 1],& not\ choose \end{array} \right. \end{aligned} max[j]ans[j]=MAX{max[j1]+nums[j],nums[j],max[j1]0max[j1]<0=MAX{max[j],ans[j1],choose jnot choose

  每次纳入 nums[j] 并考虑:

  • max[j - 1] < 0,则直接从 j 开始就好,即设置 max[j] = 0。因为算上前面的序列,和只会更小。
  • max[j - 1] >= 0,则 max[j - 1] 直接加上 nums[j] 就是以 j 结尾的最大连续和 max[j],左端起点不会发生改变。
  • max[j]ans[j - 1] 比较,ans[j] 结果取最大值。

  理论上需要开辟一个 O(n) 数组存储 max,但是由于只需要求 max 的最大值 ans,因此可以边计算边更新 ans,省去了 O(n) 的空间。

public class Solution {
	public int MaxSubArray(int[] nums) {
        int ans = nums[0], max = ans;

        for (var j = 1; j < nums.Length; j++) {
            if (max < 0) max = 0;     // 先前的序列如果 < 0,则直接抛弃,从第 j 位开始重新计数
            max += nums[j];           // 并入第 j 位
            if (max > ans) ans = max; // 更新结果
        }

        return ans;
    }
}
  • 时间:84 ms,击败 61.11% 使用 C# 的用户
  • 内存:38.23 MB,击败 77.78% 使用 C# 的用户

  使用分治可以实现 O(logn) 的复杂度。将数组 nums 一分为二,记为 left 和 right。则 nums 的答案 Max 可能有如下 3 中情况:

  1. 在 left 中。
    LeetCode 面试题 16.17. 连续数列,LeetCode写题记录,leetcode,算法,职场和发展,c#
  2. 在 right 中。
    LeetCode 面试题 16.17. 连续数列,LeetCode写题记录,leetcode,算法,职场和发展,c#
  3. 在 left 和 right 交界处。
    LeetCode 面试题 16.17. 连续数列,LeetCode写题记录,leetcode,算法,职场和发展,c#

  因此,需要记录区间的左端最大连续和 LMax(红色) 与右端最大连续和 RMax(黄色),其对应的更新情况如下:文章来源地址https://www.toymoban.com/news/detail-744961.html

  • LMax:
    LeetCode 面试题 16.17. 连续数列,LeetCode写题记录,leetcode,算法,职场和发展,c#
  • RMax:
    LeetCode 面试题 16.17. 连续数列,LeetCode写题记录,leetcode,算法,职场和发展,c#
      同时,使用 Sum(绿色)记录区间的总长度。
public class Solution {
    public struct Range
    {
        public int LMax; // 从左端开始的最长连续和
        public int RMax; // 以右端结尾的最长连续和
        public int Sum;  // 区间总和
        public int Max;  // 区间内最长连续和

        public Range(int l, int r, int s, int m) {
            LMax = l;
            RMax = r;
            Sum = s;
            Max = m;
        }

        public static Range operator +(Range left, Range right) {
            int lMax = Math.Max(left.LMax, left.Sum + right.LMax);
            int rMax = Math.Max(right.RMax, left.RMax + right.Sum);
            int sum  = left.Sum + right.Sum;
            int max  = Math.Max(Math.Max(left.Max, right.Max), left.RMax + right.LMax);
            return new Range(lMax, rMax, sum, max);
        }
    }

    public int MaxSubArray(int[] nums) {
        return Partition(nums, 0, nums.Length - 1).Max;
    }

    public Range Partition(int[] nums, int i, int j) {
        if (i == j) return new Range(nums[i], nums[i], nums[i], nums[i]);
        int mid = (i + j) >> 1;
        return Partition(nums, i, mid) + Partition(nums, mid + 1, j);
    }
}
  • 时间:76 ms,击败 94.44% 使用 C# 的用户
  • 内存:38.25 MB,击败 77.78% 使用 C# 的用户

到了这里,关于LeetCode 面试题 16.17. 连续数列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • LeetCode 面试题 16.08. 整数的英语表示

      给定一个整数,打印该整数的英文描述。 示例 1: 输入: 123 输出: “One Hundred Twenty Three” 示例 2: 输入: 12345 输出: “Twelve Thousand Three Hundred Forty Five” 示例 3: 输入: 1234567 输出: “One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven” 示例 4: 输入: 1234567891 输出: “One Billi

    2024年02月06日
    浏览(31)
  • 【LeetCode: 面试题 17.24. 最大子矩阵 | 动态规划 】

    🚀 算法题 🚀 🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀 🌲 越难的东西,越要努力坚持,因为它具有很高的价值,算法就是这样✨ 🌲 作者简介:硕风和炜,CSDN-Java领域优质创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文

    2024年02月06日
    浏览(70)
  • LeetCode 面试题 17.08 —— 马戏团人塔

    首先,我们对人的身高按照从小到大排序, 特别注意,对于身高相等的人,要按照体重从高到低排序 。这时候,序列已经满足了在上面的人要比下面的人矮一点,然后,我们只需要保证提取到一个最长的体重的上升子序列即可。这一步骤也就是 LeetCode 300——最长上升子序列

    2024年04月28日
    浏览(28)
  • LeetCode讲解篇之面试题 16.25. LRU 缓存

    设计和构建一个“最近最少使用”缓存,该缓存会删除最近最少使用的项目。缓存应该从键映射到值(允许你插入和检索特定键对应的值),并在初始化时指定最大容量。当缓存被填满时,它应该删除最近最少使用的项目。 它应该支持以下操作: 获取数据 get 和 写入数据 put 。

    2024年02月09日
    浏览(48)
  • 78-快速排序练习-LeetCode面试题17.14.最小k个数

    题目 设计一个算法,找出数组中最小的k个数。以任意顺序返回这k个数均可。 示例: 输入: arr = [1,3,5,7,2,4,6,8], k = 4 输出: [1,2,3,4] 提示:     0 = len(arr) = 100000     0 = k = min(100000, len(arr)) 思路 注意到题目要求「任意顺序返回这 k 个数即可」,因此我们只需要确保前 k 小的

    2023年04月12日
    浏览(31)
  • 【每日一题】Leetcode - 面试题 17.08. Circus Tower LCCI

    Leetcode - 面试题 17.08. Circus Tower LCCI Sorting heights to be ascending order and weights to be descending order. dp[i] = j represents person[i] as the bottom of tower, the tower height is amount of j, to calculate the dp[i] we find the maximum of dp[0 ~ (i-1)] what the person[0 ~ (i-1)] shorter and lighter than person[i], increase it of one, it’s th

    2024年02月13日
    浏览(44)
  • 【LeetCode力扣】面试题 17.14. 最小K个数(top-k问题)

    目录 1、题目介绍 2、解题思路 2.1、优先队列解法 2.2、top-k问题解法 原题链接: 面试题 17.14. 最小K个数 - 力扣(LeetCode)  题目要求非常简短,也非常简单,就是求一组数中的k个最小数。         如果在正常刷题过程中遇到这种题,那么这道题毋庸置疑是秒杀题,使用最

    2024年01月25日
    浏览(41)
  • (C语言版)力扣(LeetCode)面试题 17.04. 消失的数字5种解法

    该题目取自力扣(LeetCode)面试题 17.04. 消失的数字 链接:消失的数字 该题目主要考察时间复杂度的把握,题目如下: 数组nums包含从0到n的所有整数,但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗? 注意:本题相对书上原题稍作改动 示例

    2023年04月14日
    浏览(39)
  • Leetcode面试经典150题刷题记录 —— 数学篇

    Leetcode面试经典150题刷题记录-系列 Leetcod面试经典150题刷题记录——数组 / 字符串篇 Leetcod面试经典150题刷题记录 —— 双指针篇 Leetcod面试经典150题刷题记录 —— 矩阵篇 Leetcod面试经典150题刷题记录 —— 滑动窗口篇 Leetcod面试经典150题刷题记录 —— 哈希表篇 Leetcod面试经典

    2024年01月21日
    浏览(58)
  • Leetcode面试经典150题刷题记录 —— 矩阵篇

    Leetcod面试经典150题刷题记录-系列 Leetcod面试经典150题刷题记录——数组 / 字符串篇 Leetcod面试经典150题刷题记录 —— 双指针篇 本篇 Leetcod面试经典150题刷题记录 —— 矩阵篇 Leetcod面试经典150题刷题记录 —— 滑动窗口篇 Leetcod面试经典150题刷题记录 —— 哈希表篇 Leetcod面试

    2024年01月16日
    浏览(56)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包