贪心算法、动态规划和线段树，求解最大子数组和，解释子数组、子序列和字串的区别。

区分子数组、子序列和字串

项目	子数组	子序列	字串
连续	是	否	是
可以为空	否	否	是

子数组：

• 连续
• 至少 1 个 子序列
• 不连续
• 至少 1 个 子串 -连续
• 可以为空

贪心算法

适用条件：

• 最优化原理：具备局部最优解
• 贪心选择性质：局部最优解可达成整体最优解

动态规划

适用条件：

• 最优化原理：具备局部最优解
• 子问题重叠：问题可拆解为重复的子问题
• 无后效性：发展仅有当前状态有关，与如何来到当前状态无关

线段树

• 思想：分治
• 二叉搜索树：将区间拆分为单元区间
• 叶子节点：即单元区间

关系

• 适用贪心算法，通常也适用动态规划
• 线段树常用于处理区间拆分、合并、查询问题

例题

53. 最大子数组和
剑指 Offer 42. 连续子数组的最大和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 子数组 是数组中的一个连续部分。

答案

贪心算法

贪心策略：如果之前和小于 0，舍弃（重置为 0）

var maxSubArray = function(nums) {
  const n = nums.length
  let preSum = r = nums[0]
  for (let i = 1; i < n; i++) {
    if (preSum < 0) preSum = 0
    r = Math.max(r, preSum += nums[i])
  }
  return r
};

动态规划

状态：dp[i] 遍历到 i 元素时的最大和 状态转换：如果 dp[i - 1] 小于 0，舍弃

var maxSubArray = function(nums) {
  const n = nums.length
  const dp = new Int32Array(n)
  dp[0] = nums[0]
  let r = nums[0]
  for (let i = 1; i < n; i++) {
    dp[i] = Math.max(nums[i], dp[i - 1] + nums[i])
    r = Math.max(r, dp[i])
  }
  return r
};

动态规划 · 优化

• 单变量压缩空间

var maxSubArray = function(nums) {
  const n = nums.length
  let sum = r = nums[0]
  for (let i = 1; i < n; i++) {
    sum = Math.max(nums[i], sum + nums[i])
    r = Math.max(r, sum)
  }
  return r
};

• 用比较运算符代替频繁的 Math.max

var maxSubArray = function(nums) {
  const n = nums.length
  let sum = r = nums[0]
  for (let i = 1; i < n; i++) {
    if (sum + nums[i] > nums[i]) {
      sum += nums[i]
    } else {
      sum = nums[i]
    }
    if (r < sum) r = sum
  }
  return r
};

线段树

var maxSubArray = function(nums) {
  const d = (l, r) => {
    if (l === r) return new SegmentTreeNode(nums[l], nums[l], nums[l], nums[l])
    const m = l + r >> 1
    const left = d(l, m)
    const right = d(m + 1, r)
    const sum = left.sum + right.sum
    const leftSum = Math.max(left.leftSum, left.sum + right.leftSum)
    const rightSum = Math.max(right.rightSum, right.sum + left.rightSum)
    const maxSum = Math.max(Math.max(left.maxSum, right.maxSum), left.rightSum + right.leftSum)
    return new SegmentTreeNode(sum, leftSum, rightSum, maxSum)
  }
  return d(0, nums.length - 1).maxSum
};
class SegmentTreeNode {
  constructor (sum = 0, leftSum = 0, rightSum = 0, maxSum = 0) {
    this.sum = sum
    this.leftSum = leftSum
    this.rightSum = rightSum
    this.maxSum = maxSum
  }
}