绝妙的算法——最大子序列和问题VIP免费

本 文 分 析 并 演 示 最 大 子 序 列 和 问 题 的 几 种 算 法 ， 它 们 都 能 解 决 问 题 ， 但 是 时 间 复 杂 度 却 大相 径 庭 ， 最 后 将 逐 步 降 低 至 线 性 。 算 法 子 序 列 和 问 题 的 引 入 给定（可能 有负数）整数序 列A1, A2, A3..., An， 求这个序 列 中子 序 列 和 的 最 大值。（为方便起见， 如果所有整数均为负数， 则最 大 子 序 列 和 为 0）。例如：输入整数序 列 ： -2, 11, 8, -4, -1, 16, 5, 0， 则输出答案为 35， 即从 A2～A6。 这个问 题 之所以有吸引力， 主要是 因为存在求解 它 的 很多算 法 ， 而这些算 法 的 性 能差异又很大 。这些算 法 ， 对于少量的 输入差别都 不大 ， 几 个算 法 都 能 在瞬间 完成， 这时 若花费大 量的 努力去设计聪明的 算 法 恐怕就不太值得了；但 是 如果对于大 量的 输入， 想要更快的 获取处理结果， 那么设计精良的 算 法 显得很有必要。 切入正题 下面先提供一个设计最 不耗时 间 的 算 法 ， 此算 法 很容易设计， 也很容易理解 ， 但 对于大 量的 输入而言， 效率太低 ： 算 法 一： public static int maxSubsequenceSum(int[] a) { int maxSum = 0; for(int i=0; i maxSum) maxSum = thisSum; } } return maxSum; } 上 述 设 计 很 容 易 理 解 ， 它 只 是 穷 举 各 种 可 能 的 结 果 ， 最 后 得 出 最 大 的 子 序 列 和 。 毫 无 疑 问 ， 这个 算 法 能 够 正 确 的 得 出 和 ， 但 是 如 果 还 要 得 出 是 哪 个 子 序 列 ， 那 么 这 个 算 法 还 需 要 添 加 一 些 额 外的 代 码 。 现 在 来 分 析 以 下 这 个 算 法 的 时 间 复 杂 度 。 运 行 时 间 的 多 少 ， 完 全 取 决 于 第6、7 行 ， 它 们由一个 含有三重嵌套 for 循环中的O(1)语句组成：第3 行 上 的 循环大 小为 N...