动态规划解法：最大连续子序列和与作业调度问题

动态程序设计是一种在编程中广泛应用的方法，它特别适用于解决具有重叠子问题和最优子结构的问题，通过递归或自底向上的策略来寻找问题的全局最优解。在这份文档中，主要关注的是两个示例题目，它们都是关于最大连续子序列和的计算。 首先，我们来看例题1——求最大连续子序列的和。该问题的输入是一个包含n（不超过500）个整数的序列，目标是找到这个序列中的最大连续子序列之和。算法的核心思想是利用动态规划，维护两个变量：max（当前子序列的最大和）和m（更新后的子序列和）。遍历整个序列，如果当前元素与前一个元素相加后值更大，则更新m；若不，说明连续子序列结束，比较m和max，取较大者作为新的max。最后输出max即为所求。 代码中定义了几个关键变量，如n、i、j、m和max，以及文件句柄f和f0用于读取输入和输出结果。程序使用循环逐行读取输入文件，计算每个子序列的和，并在遇到负数时重新开始计数，以确保找到连续的正数子序列。每次循环结束后，检查更新的m是否大于当前的最大值max，如果有则更新max。当读取完整个输入文件后，输出最大连续子序列和至输出文件。 例题2则涉及更复杂的任务调度问题，即在两台机器A和B上分配n个作业，每个作业在不同机器上的完成时间不同。这里没有给出具体的ai和bi数组，但假设每个作业的处理时间已知，且不能将作业拆分或同时在两台机器上执行。程序的目标是找到使得所有作业完成所需的最短时间。此问题可以使用贪心算法或更加复杂的时间复杂度为O(n log n)的动态规划方法来解决，如匈牙利算法或两阶段贪心策略。 在这个例子中，程序可能包含一个二维数组来存储每个作业在每台机器上的处理时间，然后通过比较和选择在最短时间内完成作业的机器来逐步优化整体调度方案。最后输出总的最短处理时间。 总结起来，这两个示例展示了动态编程在求解最优化问题中的应用，例题1着重于连续子序列问题，而例题2则涉及到更复杂的资源调度问题。动态规划通过分解问题、保存中间结果并利用这些信息来避免重复计算，为这类问题提供了高效且有效的解决方案。