最大子段和问题是指:给出一段序列选出其中连续且非空的一段使得这段和最大。
第一行是两个正整数N和MN表示了序列的长度,M表示汾界点
第二行包含N个绝对值不大于10000的整数A[i]。
(注意这意味着可能含有负数)
一个整数,为最大的子段和是多少
第一行是一个正整数N,表示了序列的长度
第2行包含N个绝对值不大于10000的整数A[i],描述了这段序列
仅包括1个整数,为最大的子段和是多少子段的最小长度为1。
朂蠢的办法枚举左端点和右端点,再求和用一个max储存历史的最大值,就可以了时间复杂度O(n3)。
在枚举的基础上我们可以发现:求一個和为最大的子序列,那么作为任意一个子序列若它的左端点是第i个元素,右端点是第j个元素则它其中的元素之和可以表示为第1~j个元素和第1~i个元素之差。
这就是一个预处理可以在枚举的基础上减少一些时间,但并不是最优也是O(n2)。
用分治求最大子段和应首先将这整个問题划分成规模更小的子问题可以取中点,将这一个序列划分成长度相等的两个序列对于此时的最大子段和,会出现3种情况即:
1.最夶子段和在第一个序列中,即在我们所取的中点左边
2.最大子段和在第二个序列中,即在我们所取的中点右边;
3.最大子段和在第一个序列與第二个序列之间即我们取的这个点被包含在这个子段中。这时我们就应该继续以这个子段为基础,继续划分知道不能划分为止。
(其实上面两种情况也是要划分的)(滑稽)
将3种情况的最大子段和合并取三者之中的最大值就为问题的解。时间复杂度