[2020多校A层11.25]最大K段和

对于一个长度为n的序列，求解不相交的k段使得他们的总和最大，输出最大值。
n<=1e5

对于这种问题，我们没有思路求解，可以考虑枚举，发现无法枚举，然后考虑dp，发现可以得到一个大概$O(n^3/n^2)$的做法，然后没法继续优化了，没有更多的性质了。
因为题面没有更多的性质了，那么我们再转换思路，考虑贪心求解，于是我们按照贪心的思路，每次求解当前的最大子段和，然后如果直接这样肯定是不行的，所以我们需要支持让最大二段和变成最大子段和问题，然后我们通过这个过程使得贪心的当前最优解变成更大规模的最优解。然后其实这是一个套路，就是求解多个东西总和的最大值，然后要满足一定要求，也就是说彼此之间是有影响的。

然后这道题的反悔策略就是让当前的最大子段和变为负数，然后这样的最大子段和就含有将其删掉的部分了。然后具体地我们需要证明当前最大子段和一定是最大二段和，因为最大子段和有任意前缀后缀为正的性质，所以变为负数之后，任意前缀后缀为负数，所以现在的最大子段和一定和原来的最大子段和不会相交，只可能再最大子段和内部或者外部，所以我们证明了当前的最大子段和是最大二段和，那么重复这个过程就可以得到最大k段和。

所以需要支持查询最大子段和和区间取相反数的操作，所以线段树可以支持，让每个线段树维护当前区间的正信息和反信息，然后区间修改就让正反交换，然后打标记处理。

总结

以上是生活随笔为你收集整理的[2020多校A层11.25]最大K段和（反悔贪心）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。