题目大意: 给定一段数字序列(有正负),求最大的子串和以及该子串的始末位置。 解决: 使用在线处理方法处理最大子串和,时间复杂度O(N) 设置临时最大和sum,最大和max 遍历数字序列将a[i]累加到sum 1.若sum > max, 则更新max值和子串尾下标 2.若sum <= max, 则继续向后累加 遍历过程中,当发现sum < 0时,使sum=0并将子串起点下标后移 附:因为序列中每个数字仅被处理一次,所以复杂度O(N) 代码 [crayon-66f8aeb…
题目大意: 给定一段数字序列(有正负),求最大的子串和以及该子串的始末位置。 解决: 使用在线处理方法处理最大子串和,时间复杂度O(N) 设置临时最大和sum,最大和max 遍历数字序列将a[i]累加到sum 1.若sum > max, 则更新max值和子串尾下标 2.若sum <= max, 则继续向后累加 遍历过程中,当发现sum < 0时,使sum=0并将子串起点下标后移 附:因为序列中每个数字仅被处理一次,所以复杂度O(N) 代码 [crayon-66f8aeb…
动态规划一直是ACM竞赛中的重点,同时又是难点,因为该算法时间效率高,代码量少,多元性强,主要考察思维能力、建模抽象能力、灵活度。 ****************************************************************************************** 动态规划(英语:Dynamic programming,DP)是一种在数学、计算机科学和经济学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和最优子结…
学计算机的人是幸福的,因为在这个领域中有如此多的通俗易懂(相对来说)的经典好书,你需要做的只是坚持把它们一本一本读下去而已。在这里列出一些我看过或者准备看的算法书籍,以供参考。 1. CLRS 算法导论 算法百科全书,只做了前面十几章的习题,便感觉受益无穷。 2. Algorithms 算法概论 短小精悍,别据一格,准经典之作。一个坏消息: 同算法导论,该书没有习题答案。好消息:习题很经典,难度也适中,只需花点点时间自己也都能做出来。另有中文版名《算法概论》,我没看过,不知道翻译得怎么样。如果有心的话,还是尽量看原…