《劍指Offer》- 連續子數組的最大和或最小和

2020 年 4 月 29 日
筆記
javascript, 前端, 數據結構, 演算法

前言

本文是《劍指Offer》系列（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)

這個了解了不…

後記

以上就是胡哥今天給大家分享的內容，喜歡的小夥伴記得點贊、收藏呦，關注胡哥有話說，學習前端不迷路，歡迎多多留言交流…

胡哥有話說，一個有技術，有情懷的胡哥！現任京東前端攻城獅一枚。

胡哥有話說，專註於大前端技術領域，分享前端系統架構，框架實現原理，最新最高效的技術實踐！

Tags: javascript 前端數據結構演算法