最大子列问题（Maximum Subarray Problem）

最大子列问题（Maximum Subarray Problem）是一个经典的算法问题，它要求找出一个序列中和最大的连续子序列。这个问题可以用不同的方法解决，包括暴力法、分治法、动态规划等，其中动态规划方法最为高效，时间复杂度为O(n)。

问题描述： 给定一个整数数组nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例：假设我们有数组nums = [-2,1,-3,4,-1,2,1,-5,4]，最大子列为[4,-1,2,1]，其最大和为6。

解体思路

暴力法： git地址 (opens new window)

解体思路

我们需要遍历数组的所有可能子列，并计算它们的和，然后找到最大的那个和。 暴力法的时间复杂度是O(n^3)，因为它涉及到三层嵌套循环：外两层循环用来确定子列的起始和结束位置，内层循环用来计算子列的和。

let list = [-2,1,-3,4,-1,2,1,-5,4];

function getMaximum(list) {
  let maximum = 0;
  let listLength = list.length;
  for (let i = 0; i < listLength; i++) {
    for (let j = i; j < listLength; j++) {
      let sum = 0
      for (let k = i; k < j; k++) {
        sum += list[k];
      }
      if (sum > maximum) maximum = sum
    }
  }
  return maximum;
}

const maximum = getMaximum(list)
console.log(maximum);

• 这段代码通过三层循环遍历数组的所有可能子列，计算每个子列的和，并不断更新最大和。
• 请注意，虽然这种方法可以正确解决问题，但由于其低效的时间复杂度，它不适用于处理大规模数据。
• 在实际应用中，推荐使用更高效的算法，如Kadane算法，它的时间复杂度为O(n)。

分治法：git地址 (opens new window)

解体思路

分治法是解决最大子列问题的一种有效方法，其基本思想是将一个大问题分解成小问题逐个击破。对于最大子列问题，可以将数组分成两半，分别求解左半部分和右半部分的最大子列和，以及跨越中点的最大子列和，然后取这三者中的最大值作为整个数组的最大子列和。这种方法的时间复杂度是O(n log n)。

function maxCrossingSum(arr, left, mid, right) {
  let sum = 0;
  let leftSum = 0;
  // 包括中点的左半部分的最大子列和
  for (let i = mid; i >= left; i--) {
    sum += arr[i];
    if (sum > leftSum) leftSum = sum;
  }

  sum = 0;
  let rightSum = 0;
  // 包括中点的右半部分的最大子列和
  for (let i = mid + 1; i <= right; i++) {
    sum += arr[i];
    if (sum > rightSum) rightSum = sum;
  }

  // 返回跨越中点的最大子列和
  return leftSum + rightSum;
}

function maxSubArraySum(arr, left, right) {
  // 基本情况
  if (left == right) {
    return arr[left];
  }

  // 找到中点
  let mid = Math.floor((left + right) / 2);

  // 返回以下三者中的最大值：
  // 1. 左半部分的最大子列和
  // 2. 右半部分的最大子列和
  // 3. 跨越中点的最大子列和
  return Math.max(
    maxSubArraySum(arr, left, mid),
    maxSubArraySum(arr, mid + 1, right),
    maxCrossingSum(arr, left, mid, right)
  );
}

// 示例
const list = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
console.log(maxSubArraySum(list, 0, list.length - 1)); // 输出最大子列和，例如上述数组的最大子列和为6

这段代码首先定义了maxCrossingSum函数，用于计算跨越中点的最大子列和。然后，maxSubArraySum函数通过递归地将数组分成更小的部分，分别求解左半部分和右半部分的最大子列和，以及跨越中点的最大子列和，最后取这三者中的最大值作为结果。这种分而治之的策略使得问题得以有效解决。

在线处理【动态规划（Kadane算法）】：git地址 (opens new window)

解体思路

动态规划是解决最大子列问题的一种高效方法，其中Kadane算法是最著名的实现之一。 Kadane算法的核心思想是遍历数组，同时计算当前最大子列和，如果当前最大子列和变成负数，则从下一个元素重新开始计算。这种方法的时间复杂度是O(n)，是解决这个问题的最快方法之一。

基础方法

const list = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
function getMaximum(list) {
  let maximum = 0;
  const l = list.length;
  let sum = 0;
  for (let i = 0; i < l; i++) {
    sum += list[i];
    if (sum < 0) {
      sum = 0;
    }
    if (sum > maximum) {
      maximum = sum;
    }
  }
  return maximum;
}

const maximum = getMaximum(list);
console.log(maximum);

也可以用下main方法实现

function getMaximum_1(list) {
  let maximum = list[0];
  const l = list.length;
  let sum = list[0];
  for (let i = 0; i < l; i++) {
    sum = Math.max(list[i], sum + list[i]);
    maximum = Math.max(sum, maximum);
  }
  return maximum;
}

const maximum_1 = getMaximum_1(list);
console.log(maximum_1);

Kadane算法优点：

• 时间效率高：Kadane算法的时间复杂度为O(n)，其中n是数组的长度。这意味着算法只需要遍历数组一次就可以找到最大子数组和，这是解决这类问题的最快方法之一。
• 空间效率高：Kadane算法只需要O(1)的额外空间，因为它在遍历数组的过程中只维护了几个变量来存储中间计算结果，如当前元素之前的最大子数组和和全局最大子数组和。
• 实现简单：与其他算法相比，Kadane算法的实现相对简单直观。它避免了复杂的数据结构和算法技巧，使得即使是对动态规划不太熟悉的开发者也能轻松掌握。
• 广泛适用性：尽管Kadane算法最初是为解决最大子数组和问题设计的，但它的思想可以被扩展应用于解决其他类型的动态规划问题，比如寻找数组中的最大子序列乘积等。
• 优雅的处理负数情况：Kadane算法能够优雅地处理全部为负数的数组。在这种情况下，它会返回单个最大负数，这在数学上是正确的处理方式，因为任何包含多个负数的子数组和都会更小。

拓展 在线处理拓展git地址 (opens new window)

获取最大子列和、最大子列的第一个数字和最大子列最后一个数字、最大子列

let list = [-2, 11, -4, 13, -5, -2, 12,3,4,5,-12,3,12,-13,12,4,2];

// 输出最大子列和、最大子列开始和结束的数字、最大子列
function getMaximum(list) {
  let maximum = 0;
  const l = list.length;
  let sum = 0;
  let allList = [];
  for (let i = 0; i < l; i++) {
    sum += list[i];
    if (sum < 0) {
      sum = 0;
      allList = [];
    } else {
      if (sum > maximum) {
        maximum = sum;
      }
      allList = [...allList, list[i]]
    }
  }
  const startEndList = [allList[0], allList[allList.length - 1]]

  // 输出
  return {maximum, startEndList, allList};
}

console.log(getMaximum(list));
// 结果：
// {
//  maximum: 45,
//  startEndList: [ 11, 2 ],
//  allList: [
//     11, -4, 13,  -5, -2, 12,
//      3,  4,  5, -12,  3, 12,
//    -13, 12,  4,   2
//  ]
//}

获取最大子列和、最大子列的第一个数字和最大子列最后一个数字该方法存在问题

// 输出最大子列和，最大子列开始的数字和最大子列结束的数字
function findMaxSubsequence(list) {
  let maxSum = 0;
  let tempSum = 0;
  let start = 0;
  let tempStart = 0;
  let end = list.length - 1;

  let allNegative = true; // 假设所有数字都是负数

  // 遍历数组，寻找最大子序列和
  for (let i = 0; i < list.length; i++) {
    tempSum += list[i];

    // 检查是否所有数字都是负数
    if (list[i] > 0) {
      allNegative = false;
    }

    if (tempSum > maxSum) {
      maxSum = tempSum;
      start = tempStart;
      end = i;
    } else if (tempSum < 0) {
      tempSum = 0;
      tempStart = i + 1;
    }
  }

  // 如果所有数字都是负数，最大子序列和为0，返回整个序列的第一个和最后一个数字
  if (allNegative) {
    maxSum = 0;
    start = 0;
    end = list.length - 1;
  }

  return [maxSum, list[start], list[end]];
}

// 测试用例
console.log(findMaxSubsequence(list));
// 结果：[ 45, 11, 2 ]

正确的返回结果应该是： [0, 0, 0]
下面是代码

function isAllNonPositiveAndContainsZero(arr) {
  let containsZero = false;
  // 遍历数组中的每个元素
  for (let i = 0; i < arr.length; i++) {
    // 如果找到一个大于0的元素，返回false
    if (arr[i] > 0) {
      return false;
    }
    // 检查是否至少有一个元素是0
    if (arr[i] === 0) {
      containsZero = true;
    }
  }
  // 确保数组至少包含一个0
  return containsZero;
}

function getMaximum(list) {
  let maxSum = 0;
  let tempSum = 0;
  let start = 0;
  let tempStart = 0;
  let end = list.length - 1;

  let allNegative = true; // 假设所有数字都是负数
  if (isAllNonPositiveAndContainsZero(list)) {
    return [0, 0, 0];
  }

  // 遍历数组，寻找最大子序列和
  for (let i = 0; i < list.length; i++) {
    tempSum += list[i];

    // 检查是否所有数字都是负数
    if (list[i] > 0) {
      allNegative = false;
    }

    if (tempSum > maxSum) {
      maxSum = tempSum;
      start = tempStart;
      end = i;
    } else if (tempSum < 0) {
      tempSum = 0;
      tempStart = i + 1;
    }
  }

  // 如果所有数字都是负数，最大子序列和为0，返回整个序列的第一个和最后一个数字
  if (allNegative) {
    maxSum = 0;
    start = 0;
    end = list.length - 1;
  }

  return maxSum, list[start], list[end];
}