前言

本文是《劍指Offer》系列（JavaScript版）的第一篇，題目是“連續(xù)子數(shù)組的最大和或最小和”。

話不多說，開始“打怪”修煉...

一、理解題目

以“連續(xù)子數(shù)組的最大和”為例，相當(dāng)于我們在數(shù)組中，計(jì)算連續(xù)的子數(shù)組的和，找尋最大值。如在數(shù)組[3, -2, 1, 2, 4, -6, 5]中連續(xù)子數(shù)組的最大和為：3 + (-2) + 1 + 2 + 4 = 8

輸入：[3, -2, 1, 2, 4, -6, 5]
輸出：8

一定要準(zhǔn)確的理解題意，如不是特別明確，建議與面試官再次溝通確認(rèn)，避免需求與實(shí)現(xiàn)不一致的情況。

二、解決方案

連續(xù)子數(shù)組的最大和

這道面試題有幾種解決方案呢？可能在很多個同學(xué)的腦海里會出現(xiàn)這樣的一種方案：

1. 求連續(xù)子數(shù)組組合方案：

將數(shù)組中的元素進(jìn)行連續(xù)子數(shù)組的組合，每一種組合計(jì)算出一個值，依次比較后取出最大值。那這種方式是可以肯定是可以最終的效果的，But這么處理的話，會有多少種組合方案呢？

以數(shù)組 [1, -1, 2, -3, 5]為例：
    連續(xù)子數(shù)組有：N + (N-1) + (N-2)...  +  1 = n*(n+1) / 2

隨著數(shù)組長度N的值越大，組合數(shù)量肯定是越大！同時在獲取階乘后，還需要再次進(jìn)行一次最大值得比較。

劃重點(diǎn)：

此方案雖可以實(shí)現(xiàn)最終的效果，但是確實(shí)十分不可取的!

2. 最優(yōu)解方案

在面試時面試題除了固定的套路和算法外，要多嘗試邏輯思維的轉(zhuǎn)變...

技術(shù)方案：
    1. 初始化兩個變量：sum(連續(xù)子數(shù)組的累加和)、max(最大值)
    2. 遍歷數(shù)組元素，考慮sum的情況： 
        sum >= 0，將當(dāng)前元素的值進(jìn)行累加
        sum < 0，注意，sum的值為負(fù)值，不管當(dāng)前的元素值是什么，累加sum(負(fù)數(shù))肯定值最終會變小的，所以此刻，要重新對sum進(jìn)行賦值操作
    3. 每次遍歷時，都要比較sum和max的大小， 如果 sum > max，進(jìn)行賦值max = sum
    4. 返回最終的結(jié)果max

接下來，我們來看下代碼的實(shí)現(xiàn)：

/**
 * getGreatestSumOfSubArray()
 * @description 獲取連續(xù)子數(shù)組中最大和
 * @param Array arr 指定的數(shù)組
 * @returns Number sum 最大和
*/
function getGreatestSumOfSubArray (arr) {
  // 容錯邊界處理
  if (!Array.isArray(arr) || arr.length === 0) {
    return 0
  }

  // 解構(gòu)，初始獲取數(shù)組的第一個元素值
  // 注意：一定不能把sum和max設(shè)置初始化為0，必須要考慮數(shù)組元素中全部為負(fù)數(shù)的情況
  let [ sum ] = arr
  let [ max ] = arr
  
  let len = arr.length
  for (let i = 1; i < len; i++) {
    // 如果當(dāng)前sum累加 < 0，重新初始化當(dāng)前元素值；否則執(zhí)行累加
    if (sum < 0) {
      sum = arr[i]
    } else {
      sum += arr[i]
    }

    // 比較累加和與最大值
    if (sum > max) {
      max = sum
    }
  }
  
  return max
}

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

OK，這樣我們就實(shí)現(xiàn)了需求，小朋友，你還有問號嗎？

連續(xù)子數(shù)組的最小和

“連續(xù)子數(shù)組的最小和” 這個需求的實(shí)現(xiàn)原理和“連續(xù)子數(shù)組的最大和”的實(shí)現(xiàn)基本是一致的，唯一的區(qū)別點(diǎn)為：當(dāng)sum的值 > 0為正數(shù)時，累加就無意義了，需要重新賦值為當(dāng)前值。我們來看下代碼的實(shí)現(xiàn)

/**
 * getLeastSumOfSubArray()
 * @description 獲取連續(xù)子數(shù)組的最小和
 * @param Array arr 指定的數(shù)組
 * @returns Number min 最小和
*/
function getLeastSumOfSubArray (arr) {
  if (!Array.isArray(arr) || arr.length === 0) {
    return 0
  }

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

  // 遍歷數(shù)組元素，如果sum是一個正數(shù)，累加就無意義，重新賦值為當(dāng)前項(xiàng)；
  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)

這個了解了不...

后記

以上就是胡哥今天給大家分享的內(nèi)容，喜歡的小伙伴記得點(diǎn)贊、收藏呦，關(guān)注胡哥有話說，學(xué)習(xí)前端不迷路，歡迎多多留言交流...

胡哥有話說，一個有技術(shù)，有情懷的胡哥！現(xiàn)任京東前端攻城獅一枚。

胡哥有話說，專注于大前端技術(shù)領(lǐng)域，分享前端系統(tǒng)架構(gòu)，框架實(shí)現(xiàn)原理，最新最高效的技術(shù)實(shí)踐！