面试官在“逗”你系列:连续子数组的最大和或最小和

胡哥有话说 等级 341 0 0

前言

本文题目是“连续子数组的最大和或最小和”。

话不多说,开始“打怪”修炼...

一、理解题目

以“连续子数组的最大和”为例,相当于我们在数组中,计算连续的子数组的和,找寻最大值。如在数组[3, -2, 1, 2, 4, -6, 5]中连续子数组的最大和为:3 + (-2) + 1 + 2 + 4 = 8

输入:[3, -2, 1, 2, 4, -6, 5]
输出:8

一定要准确的理解题意,如不是特别明确,建议与面试官再次沟通确认,避免需求与实现不一致的情况。

二、解决方案

连续子数组的最大和

这道面试题有几种解决方案呢?可能在很多个同学的脑海里会出现这样的一种方案:

1. 求连续子数组组合方案:

将数组中的元素进行连续子数组的组合,每一种组合计算出一个值,依次比较后取出最大值。那这种方式是可以肯定是可以最终的效果的,But这么处理的话,会有多少种组合方案呢?

以数组 [1, -1, 2, -3, 5]为例:
    连续子数组有:N + (N-1) + (N-2)...  +  1 = n*(n+1) / 2

随着数组长度N的值越大,组合数量肯定是越大!同时在获取阶乘后,还需要再次进行一次最大值得比较。

划重点:

此方案虽可以实现最终的效果,但是确实十分不可取的!

2. 最优解方案

在面试时面试题除了固定的套路和算法外,要多尝试逻辑思维的转变...

技术方案:
    1. 初始化两个变量:sum(连续子数组的累加和)、max(最大值)
    2. 遍历数组元素,考虑sum的情况: 
        sum >= 0,将当前元素的值进行累加
        sum < 0,注意,sum的值为负值,不管当前的元素值是什么,累加sum(负数)肯定值最终会变小的,所以此刻,要重新对sum进行赋值操作
    3. 每次遍历时,都要比较sum和max的大小, 如果 sum > max,进行赋值max = sum
    4. 返回最终的结果max

接下来,我们来看下代码的实现:

/**
 * getGreatestSumOfSubArray()
 * @description 获取连续子数组中最大和
 * @param Array arr 指定的数组
 * @returns Number sum 最大和
*/
function getGreatestSumOfSubArray (arr) {
  // 容错边界处理
  if (!Array.isArray(arr) || arr.length === 0) {
    return 0
  }

  // 解构,初始获取数组的第一个元素值
  // 注意:一定不能把sum和max设置初始化为0,必须要考虑数组元素中全部为负数的情况
  let [ sum ] = arr
  let [ max ] = arr

  let len = arr.length
  for (let i = 1; i < len; i++) {
    // 如果当前sum累加 < 0,重新初始化当前元素值;否则执行累加
    if (sum < 0) {
      sum = arr[i]
    } else {
      sum += arr[i]
    }

    // 比较累加和与最大值
    if (sum > max) {
      max = sum
    }
  }

  return max
}

// 调用
let max = getGreatestSumOfSubArray([3, -2, 1, 2, 4, -6, 5])
console.log(max) // 8

OK,这样我们就实现了需求,小朋友,你还有问号吗?

连续子数组的最小和

“连续子数组的最小和” 这个需求的实现原理和“连续子数组的最大和”的实现基本是一致的,唯一的区别点为:当sum的值 > 0为正数时,累加就无意义了,需要重新赋值为当前值。我们来看下代码的实现

/**
 * getLeastSumOfSubArray()
 * @description 获取连续子数组的最小和
 * @param Array arr 指定的数组
 * @returns Number min 最小和
*/
function getLeastSumOfSubArray (arr) {
  if (!Array.isArray(arr) || arr.length === 0) {
    return 0
  }

  // 初始化
  let [ sum ] = arr
  let [ min ] = arr

  // 遍历数组元素,如果sum是一个正数,累加就无意义,重新赋值为当前项;
  let len = arr.length
  for (let i = 1; i < len; i++) {
    if (sum > 0) {
      sum = arr[i]
    } else {
      sum += arr[i]
    }
    if (sum < min) {
      min = sum
    }
  }

  return min
}

let min = getLeastSumOfSubArray([-1, -2, 3, 2, -4, -8])
console.log(min) // -12 = (-4) + (-8)

这个了解了不...

后记

以上就是胡哥今天给大家分享的内容,喜欢的小伙伴记得点赞收藏呀,关注胡哥有话说,学习前端不迷路,欢迎多多留言交流...

胡哥有话说,专注于大前端技术领域,分享前端系统架构,框架实现原理,最新最高效的技术实践!

收藏
评论区

相关推荐

面试官在“逗”你系列:数组去重你会几种呀?
前言 数组去重是一个老生常谈的话题,也是前端童鞋在面试时的一道高频题。本文将深入的探索数组去重的原理及实现,为各位小伙伴提供多种可以反手“调戏”面试官的解决方案。 话不多说,上去就来一梭子... 数组去重核心原理 价值100W的核心原理上来就给你了...,记得留言点赞鸭! 1. 一般我们都会创建临时变量tmp,存储不重复的元素(以数组元素存储或对
面试官在“逗”你系列:连续子数组的最大和或最小和
前言 本文题目是“连续子数组的最大和或最小和”。 话不多说,开始“打怪”修炼... 一、理解题目 以“连续子数组的最大和”为例,相当于我们在数组中,计算连续的子数组的和,找寻最大值。如在数组3, 2, 1, 2, 4, 6, 5中连续子数组的最大和为:3 (2) 1 2 4 8 输入:3, 2, 1, 2, 4, 6,
面试官在“逗”你系列:不借助第三变量交换两个变量值的方案你有几种?
引言 在我们学习编程之初,就学习过变量的赋值操作,同时也学习了将一个变量的值赋值给另外一个变量。对于交换两个变量的值,很多童鞋都有解决方案。然鹅,对于面试官提出的不借助第三变量来交换两个变量的值,你能想到几种解决方案呢? 如果你只知道一种方案,请你认真看下去... 如果你知道两种方案,那么你可以来了解更多方案了... 一、最简单的实现最初的记忆 让
图文并茂讲清楚 JavaScript 内存管理
作为一个 JavaScript 的开发者,大多数情况下你可能不会担心内存管理问题,因为 JavaScript 引擎会帮你处理这些。但是在开发过程中,你或多或少的会遇到一些相关的问题,比如内存泄漏等,只有了解了内存分配的工作机制,你才会知道如何去解决这些问题。 在这篇文章中,我将会向你介绍 内存分配 和 垃圾收集 的机制,以及如何避免一些 常见的内存泄漏 的
Hook 规则 – React
Hook 规则_Hook_ 是 React 16.8 的新增特性。它可以让你在不编写 class 的情况下使用 state 以及其他的 React 特性。Hook 本质就是 JavaScript 函数,但是在使用它时需要遵循两条规则。我们提供了一个 来强制执行这些规则: 只在最顶层使用 Hook不要在循环,条件或嵌套函数中调用 Hoo
TypeScript 4.2 有哪些新特性
TypeScript 4.2 发布了!对于不熟悉 TypeScript 的人来说,TypeScript 就是增加了静态类型和类型检查的 JavaScript。有了类型限制,你就可以精确的表达你的函数需要什么类型的参数以及返回什么类型的结果。同时,利用 TypeScript 的类型检查,你可以很容易避免一些常见错误,例如拼写错误或者忘记处理 null 和 un
你可能不知道的10个CSS新功能(2021版)
多年来,CSS已经超越了背景颜色、边框、文本样式、边距和盒模型。现代CSS能够提供一系列的功能,而在过去,您需要JavaScript或变通方法来实现这些功能。 为了庆祝它在2021年取得的成就,在这篇文章中,我们想看看一些你可能不知道的令人惊叹的CSS新特性。我们将强调web设计人员和开发人员可以用现代CSS做的很酷的事情,讨论用例,浏览器支持,并给你一个
重学JavaScript第1集|变量提升
变量提升就好比JavaScript引擎用一个很小的代码起重机将所有var声明和function函数声明都举起到所属作用域(所谓作用域,指的是可访问变量和函数的区域)的最高处。这句话的意思是:如果在函数体外定义函数或使用var声明变量。则变量和函数的作用域会提升到整个代码的最高处,此时任何地方访问这个变量和调用这个函数都不会报错;而在函数体内定义函数或使用va
了解什么是 TypeScript
内容纲要 了解什么是 TypeScript TypeScript 基本语法 TypeScript 介绍 TypeScript 是什么TypeScript 是 JavaScript 的强类型版本。然后在编译期去掉类型和特有语法,生成纯粹的 JavaScript代码。由于最终在浏览器中运行的仍然是 JavaScript,所以 TypeScript 并
Python入门教程对小白很友好
事实上想学好一门言语或许是其他任何的技术,都不可能短时间内学成,除非能够像电视剧那样把手放在背面传功,或许拿到屠龙刀里的九阴真经,让你一下子变成超级赛亚人3,消灭地球。要把Python学好,在我看来,只要相同东西能够帮你做到,那就是,爱好爱好爱好!重要的事情说三遍!在Python这个魔法世界里,找到你自己感爱好的点进行切入,并时刻找到爱好点进行自我驱动是最好
用python关对象电脑,“分手秘籍”,慎用!!!
​好多天没有跟对象吵架了,有点想练练嘴皮子功夫了,想点办法惹对象生气来。(醒醒,你没对象!) 好了,不逗了,这边教大家用python悄咪咪的控制电脑,微信来操作电脑关机(嘻嘻嘻) 学会了就可以在对象打游戏的时候,把电脑关了(谁叫他不理你,我说的不是“他”呀) 注意:感情不稳定者慎用!!! 一不小心就会..........分手吧粗体 下面是实际操作: 远程控制
几个有点意思的 CSS 技巧
如果你是一名前端开发人员或者想成为一名开发人员,那么,我今天与你分享的9个CSS技巧,你需要知道一下。现在,我们开始吧。1、学习盒子模型你在学习 CSS 时,应该避免使用Bootstrap或TailwindCSS等框架,这些工具非常适合构建漂亮的网站,但如果你还不能正确的了解 CSS,则建议不要使用这些框架中的任何一个。因为如果你使用了这些工具,你将无法学习
一个因全局变量引发的故事!
前言科比问道:“你知道洛杉矶每天早上四点钟是什么样子嘛?”,我没见过,但是我经常见广州白云区四点钟的样子。是不是在早晨阳光下看着跟随自己前行的身影道:“起的比鸡早,睡的比狗晚,或许这是我最后一次努力的挣扎”。 睡梦惊醒我有一个中午空出半个小时看书的习惯,那天中午看到1点钟的时候,确实有点困了,就急忙合上书躺椅子上睡一觉,正在做梦呢!突然一把被同事(妹子)推醒
【LeetCode每日一题 Day 5】5. 最长回文子串
大家好,我是编程熊,今天是LeetCode每日一题的第五天,一起学习LeetCode第五题《最长回文子串》。 题意给你一个字符串 s,找到 s 中最长的回文子串。示例txt输入:s "babad"输出:"bab"解释:"aba" 同样是符合题意的答案。 题解 方法一采用简单暴力的方法,枚举每一个位置为单独回文中心(长度为奇数的子串,如 aba)或者回文中心
为什么说Python是最伟大的语言?看图就知道了!
测试一下你的分析能力,直接上图,自己判断一下为什么Python是最好的语言?有图有真相 Java之父 James Goshling C++之父 Bjarne Stroustrup PHP之父 Rasmus Lerdorf Python之父 Guido van Rossum看到他们的亮点了吗? Java和C++是锃亮的电灯泡 PHP是一