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

胡哥有话说 等级 738 0 0
标签: Javascript

前言

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

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

一、理解题目

以“连续子数组的最大和”为例,相当于我们在数组中,计算连续的子数组的和,找寻最大值。如在数组[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 引擎会帮你处理这些。但是在开发过程中,你或多或少的会遇到一些相关的问题,比如内存泄漏等,只有了解了内存分配的工作机制,你才会知道如何去解决这些问题。 在这篇文章中,我将会向你介绍 内存分配 和 垃圾收集 的机制,以及如何避免一些 常见的内存泄漏 的
C++ 逗号运算符
1.逗号运算符的结果是,最后那个式子的结果 2.逗号运算符是优先级最低的,比等号的运算符优先级还低 1 int a = 2; 2 int b = 3; 3 int c = a, b++,a+b; 4 //结果是c = 2; 因为等号赋值运算符
JSON学习笔记(二、语法)
#### JSON和js关系 欲学JSON先学js,那么JSON和js的关系是什么样的呢? .JSON 使用 JavaScript 语法来描述数据对象,但是 JSON 仍然独立于语言和平台。 .JSON 语法是 JavaScript 语法的子集 #### 基本语法 .数据在名称/值对中 .数据由逗号分隔 .大括号保存对象 .中括号保
Java学习笔记(44)——Java枚举
一、枚举在Switch中的应用 --------------- public enum MyColor{    //每个枚举值用逗号隔开,    RED,    BLUE,    GREEN;//最后的分号可要或不要 } public class Test1{     public stat
Java笔试面试题(转载+自己整理)
扑克牌 === > 打牌里面经常出现的5张牌,一个顺子带一对,给你五张牌,比如:1,2,2,2,3 或者 5,6,7,4,4 或者 2,4,3,5,5 或者 7,5,9,6,9 ,这种情况就符合一个顺子带一对,则返回 true;反之比如:1,3,4,6,6 或者 1,5,5,3,4 这种返回false,请你在不能使用任何数组原生方法,只能使用循环和赋值的情
26种JavaScript优化技术
开发人员的生活总是在学习新事物。作为前端开发人员必须知道一些使我们的代码如何更优雅,工作更轻松的技巧。 也许你已经进行了很长时间的JavaScript开发,但有时你可能没有使用不需要解决或编写一些额外代码即可解决问题的最新功能。 这些技术可以帮助你编写干净且优化的JavaScript代码。 1\. 多个条件判断 ---------- // lo
Apache的Order Allow,Deny 详解
Allow和Deny可以用于apache的conf文件或者.htaccess文件中(配合Directory, Location, Files等),用来控制目录和文件的访问授权。 所以,最常用的是:      Order Deny,Allow      Allow from All 注意“Deny,Allow”中间只有一个逗号,也只能有一个逗号,有
CSV (逗号分隔值文件格式)
逗号分隔值(Comma-Separated Values,CSV,有时也称为字符分隔值,因为分隔字符也可以不是逗号),其文件以纯文本形式存储表格数据(数字和文本)。纯文本意味着该文件是一个字符序列,不含必须像二进制数字那样被解读的数据。CSV文件由任意数目的记录组成,记录间以某种换行符分隔;每条记录由字段组成,字段间的分隔符是其它字符或字符串,最常见的是逗号
ES2020 中 Javascript 10 个你应该知道的新功能
好消息 - ES2020 新功能已经落地!这就意味着,现在对 ES2020 中 Javascript 的新增和改进要有一个完整的了解。让我们来看看都有哪些改变。 **1、BigInt** ------------ BigInt,Javascript 中最期待的新功能终于落地。它允许开发者在 JS 中使用更大的整数进行数据处理。 之前,Javas
GoJS用于HTML图表的JavaScript库
[GoJS](https://www.oschina.net/action/GoToLink?url=https%3A%2F%2Fwww.evget.com%2Fproduct%2F3108)是一款功能强大,快速且轻量级的流程图控件,可帮助你在JavaScript 和HTML5 Canvas程序中创建流程图,且极大地简化您的JavaScript / Canv
JavaScript 的面向切面编程
我们都知道面向对象编程,或者至少听说过 JavaScript 领域的函数式编程,但是,你听说过面向切面编程吗? 我知道,它听起来像是《魔法战队》中某一集出现的东西。然而,AOP 是实际存在的。此外,虽然我们现在没有使用它,但它却可以被应用于我们日常会见到的一些用例中。 它最大的优势在于,你可以毫不费力的将 AOP 与 FP 或 OOP 结合使用,就像 J
JavaScript常见的10个错误
10 种最常见的 Javascript 错误 ---------------------- **以下是 JavaScript 错误 Top 10:** 为了便于阅读,我们将每个错误描述都缩短了。接下来,让我们深入到每一个错误,来确定什么会导致它,以及如何避免创建它。 **1\. Uncaught TypeError: Cannot read prope
React面试必问Fiber和Hooks,一次搞定
国内的前端领域,Vue 和 React 是最火的两个框架,要说岗位数量,Vue可能会更多一点。 但如果把公司范围缩小到大厂,或者把范围扩展到全球,那React无疑独占鳌头。 ![](https://oscimg.oschina.net/oscnet/ba57134c-6a7d-47d8-a317-7ad3976a1a77.jpg "2019年