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

胡哥有话说
• 阅读 1140

前言

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

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

一、理解题目

以“连续子数组的最大和”为例,相当于我们在数组中,计算连续的子数组的和,找寻最大值。如在数组[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)

这个了解了不...

后记

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

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

点赞
收藏
评论区
推荐文章
秃头王路飞 秃头王路飞
4个月前
webpack5手撸vue2脚手架
webpack5手撸vue相信工作个12年的小伙伴们在面试的时候多多少少怕被问到关于webpack方面的知识,本菜鸟最近闲来无事,就尝试了手撸了下vue2的脚手架,第一次发帖实在是没有经验,望海涵。languageJavaScript"name":"vuecliversion2","version":"1.0.0","desc
光头强的博客 光头强的博客
4个月前
Java面向对象试题
1、请创建一个Animal动物类,要求有方法eat()方法,方法输出一条语句“吃东西”。创建一个接口A,接口里有一个抽象方法fly()。创建一个Bird类继承Animal类并实现接口A里的方法输出一条有语句“鸟儿飞翔”,重写eat()方法输出一条语句“鸟儿吃虫”。在Test类中向上转型创建b对象,调用eat方法。然后向下转型调用eat()方
胡哥有话说 胡哥有话说
1年前
面试官在“逗”你系列:数组去重你会几种呀?
前言数组去重是一个老生常谈的话题,也是前端童鞋在面试时的一道高频题。本文将深入的探索数组去重的原理及实现,为各位小伙伴提供多种可以反手“调戏”面试官的解决方案。话不多说,上去就来一梭子...数组去重核心原理价值100W的核心原理上来就给你了...,记得留言点赞鸭!1.一般我们都会创建临时变量tmp,存储不重复的元素(以数组元素存储或对
小森森 小森森
4个月前
校园表白墙微信小程序V1.0 SayLove -基于微信云开发-一键快速搭建,开箱即用
后续会继续更新,敬请期待2.0全新版本欢迎添加左边的微信一起探讨!项目地址:(https://www.aliyun.com/activity/daily/bestoffer?userCodesskuuw5n)\2.Bug修复更新日历2.情侣脸功能大家不要使用了,现在阿里云的接口已经要收费了(土豪请随意),\\和注意
Souleigh ✨ Souleigh ✨
2年前
JS 实现单链表
要存储多个元素,数组(或列表)可能是最常用的数据结构。但这种数据结构有一个缺点:(在大多数语言中)数据的大小是固定的,从数组的起点或中间插入或移除项的成本很高。  链表存储有序的集合,但不同于数组,链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(也称指针或链接)组成。  相对于传统的数组,链表的一个好处是
孤心独饮 孤心独饮
2年前
从零开始刷力扣(一)——485:最大连续1的个数
分类:数组的遍历题目描述:给定一个二进制数组,计算其中最大连续1的个数。示例1:输入:1,1,0,1,1,1输出:3解释:开头的两位和最后的三位都是连续1,所以最大连续1的个数是3.思路初始化count和maxCount,然后遍历数组,遇见1则count,并且更新与maxCount比较,若比maxCount更大,则更新m
Stella981 Stella981
1年前
JavaScript实现字符串逆置的几种方法
1\.一般来说js实现字符串逆置输出的一般思路是:1、将字符串转为数组,一个字符为数组的一个元素; 2、将数组倒置; 3、再将数组元素拼接为字符串。2\.一般用到的方法有:join():该方法用于把数组中的所有元素放入一个字符串。元素是通过指定的分隔符进行分隔的。 split():将一个字符串分割为子字符串数
Stella981 Stella981
1年前
A Mini Locomotive(动态规划 01)
 /\ 题意:选出3个连续的数的个数 为K的区间,使他们的和最大分析: dp\j\\i\max(dp\jk\\i1\value\j\,dp\j1\\i\);dp\j\\i\:从j个数种选出i个连续区间 数值的最大和value\j\:第j个区间内的数的和和背包有点像,但要活用\
京东云开发者 京东云开发者
2个月前
为什么mysql不推荐使用雪花ID作为主键
作者:毛辰飞背景在mysql中设计表的时候,mysql官方推荐不要使用uuid或者不连续不重复的雪花id(long形且唯一),而是推荐连续自增的主键id,官方的推荐是auto_increment,那么为什么不建议采用uuid,使用uuid究
Suzhou Suzhou
1个月前
排序算法(冒泡、快速、插入)
稳定性:排序前后相等的元素位置是否会被交换。冒泡排序strcpy只能拷贝字符串,整型或浮点型数组需要用memcpy。memcpy称为内存拷贝接口,可以将某一段连续的内存放入另一段连续的内存中。在使用随机数的代码中使用固定的数组有利于调试。:::tipmem