寻找最长增长子序列

index.js

/**
 * 在一个无序数组中找出最长的连续增长片段，步长为 1
 *
 * 该算法时间复杂度为： O(n)
 * 空间复杂度为常数
 *
 * @author 陈元
 * @email cy476571@gmail.com
 */

const assert = require('assert')

/**
 * @param {Array} arr 待查找无序数组
 *
 * @return {Array} 找到的序列
 */
function findLongestIncresingSubsegment(arr = []) {
  const step = 1              // 步长

  // [start, end, length]
  let result = []             // 最长连续增长序列的起止下标
  let current = []            // 当前的连续增长序列起止下标
  let nextValueExcepted = 0   // 期望的下一个值

  if (!Array.isArray(arr) || !arr.length) {
    return result
  }

  const arrLength = arr.length
  for (let i = 0; i < arrLength; i++) {
    const item = parseInt(arr[i])

    // 该输入不是数字
    if (!item) {
      if (current.length > 1 && (!result.length || current[2] >= result[2])) {
        result = current
      }

      current = []
      continue
    }

    if (!current.length) {
      current.push(i)
      nextValueExcepted = item + step
    } else {
      if (item === nextValueExcepted) {
        current = [current[0], ...[i, i - current[0]]]
        nextValueExcepted = item + step
        continue
      }

      // 如果当前没有连续的序列，或者不是最长的，丢弃
      // 如果是相同长度的，选择后者
      if (current.length > 1 && (!result.length || current[2] >= result[2])) {
        result = current
      }

      current = [i]
      nextValueExcepted = item + step
    }
  }

  return arr.slice(result[0], result[1] + 1)
}


/**
 * Test cases
 */
(function () {
  const data = [
    {
      input: [],
      excepted: [],
    },
    {
      input: '',
      excepted: [],
    },
    {
      input: [3, 4, 2, 4, 5, 6, 1, 9],
      excepted: [4, 5, 6],
    },
    {
      input: [3, 4, 2, 4, 5, 'ab', 6, 1, 9],
      excepted: [4, 5],
    },
    {
      input: [1, 2, 3, 12, 13, 21, 22, 23, 24, 34, 35],
      excepted: [21, 22, 23, 24],
    }
  ]

  try {
    data.forEach(({ input, excepted }) => {
      assert.deepEqual(findLongestIncresingSubsegment(input), excepted)
    })

    console.log(data)
    console.log('测试全部通过')
  } catch (err) {
    console.log('测试失败')
    console.log(err)
  }
})()