lt;数据结构与算法分析gt;读书笔记--最大子序列和问题的求解

显然，算法3需要比前面两种算法更多的编程努力。然而，程序短并不总意味着程序好。正如我们在前面显示算法运行时间的表中已经看到的(可以参考这篇文章:<数据结构与算法分析>读书笔记--要分析的问题)，除最小的输入量外，该算法比前两个算法明显要快。

?

算法4:

    int maxSubSum4( [] a) {
        int maxSum = 0,thisSum = 0int j = 0;j<a.length;j++) {
           thisSum +=a[j];
           
            maxSum)
               
               maxSum = thisSum;
           else if(thisSum < 0)
               thisSum = 0;
            
        }
        
         maxSum;
    }

?

不难理解为什么时间的界是正确，但是要明白为什么算法是正确可行的却需要多加思考。为了分析原因，注意，像算法1和算法2一样，j代表当前序列的终点，而i代表当前序列的起点。碰巧的是，如果我们不需要知道具体最佳的子序列在哪里，那么i的使用可以从程序上被优化，因此在设计算法的时候假设i是需要的，而且我们想要改进算法2.一个结论是，如果a[i]是负的，那么它不可能代表最优序列的起点，因为任何包含a[i]的作为起点的子序列都可以通过用a[i+1)作起点而得到改进。类似地，任何负的子序列不可能是最优子序列的前缀。如果在内循环中检测到从a[i]到a[j]的子序列是负的，那么可以推进i。关键的结论是，我们不仅能够把i推进到i+1，而且实际上还可以把它一直推进到j+1。为了看清楚这一点，令p为i+1和j之间的任一下标。开始于下标p的任意子序列都不大于在下标i开始并包含从a[i]到a[p-1)的子序列的对应的子序列，因为后面这个子序列不是负的(j是使得从下标i开始其值成为负值的序列的第一个下标)。因此，把i推进到j+1是没有风险的:我们一个最优解也不会错过。

这个算法是许多聪明算法的典型:运行时间是明显的。但正确性则不那么容易看出来。对于这些算法，正式的正确性证明(比上面的分析更正式)几乎总是被需要的；然而，即使到那时，许多人仍然不信服。此外，许多这类算法需要更有技巧的编程，这导致更长的开发过程。不过当这些算法正常工作时，它们运行得很快，而我们将它们和一个低效的蛮力算法通过小规模的输入进行比较可以测试大部分的程序原理。

该算法的一个附带的优点是，它只对数据进行一次扫描，一旦a[i]被读入并被处理，它就不再需要被记忆。因此，如果数组在磁盘上或通过互联网传送，那么它就可以被按顺序读入，在主存中不必存储数组的任何部分。不仅如此，在任意时刻，算法都能对它已经读入的数据给出子序列问题的正确答案。具有这种特性的算法叫做联机算法。仅需要常量空间并以线性时间运行的联机算法几乎是完美的算法。

?

代码示例地址为:https://github.com/youcong1996/The-Data-structures-and-algorithms/tree/master/algorithm_analysis

（编辑：大连站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!