LeetCode-最大子序和(java实现)以及分治法理解

迷南。 2022-05-11 05:58 82阅读 0赞

题目如下：

![70][]

题目中已经给了提示，完美的解法需要使用分治法求解。本题的分治法代码实现非诚简单，但是理解起来会有点困难，先看一下这两篇博客的解释，再看代码

分治法理解：[https://blog.csdn.net/linhuanmars/article/details/21314059][https_blog.csdn.net_linhuanmars_article_details_21314059]

分治法理解：[https://blog.csdn.net/Pwiling/article/details/49405163][https_blog.csdn.net_Pwiling_article_details_49405163]

public int maxSubArray(int[] nums) {
            if(nums == null || nums.length == 0){
                return 0;
            }
            int local = nums[0];
            int global = nums[0];
            for(int i=1; i<nums.length; i++){
                local = Math.max(nums[i], local+nums[i]);
                global = Math.max(local, global);
            }
            return global;
        }

整个代码中最关键的一句代码就是循环体中的“local = Math.max(nums\[i\], local+nums\[i\]”。做完这道题目之后，我对分治法的理解是：每一步找出局部最优解，然后在这些局部最优解中找出一个全局最优解，这个全局最优解就是我们想要的结果。

这里我把程序运行的步骤图画了出来，

![70 1][]

非常感谢这两篇文章的作者，让我对分治法有了更深的理解。上面他们的解释已经很清晰了，不过这里我也想说一说我的理解。红着脸班门弄斧一下，哈哈。

从局部最优解中找出全局最优解，只需要在每次循环之后比较local和global的大小即可。难点在于理解“local = Math.max(nums\[i\], local+nums\[i\]”这行代码。为什么寻找局部最优解(最大子序和)是比较nums\[i\]和local+nums\[i\]的值就行了呢？

根据表达式等号左边的“local”要么等于nums\[i\]，要么等于local+nums\[i\]。而等号右边的local+nums\[i\]其实就是数组的一个子序。 当程序运行到第i次的时候，假设当前最大子序和是local+nums\[i\]。第i+1次与第i次相比，多了一个nums\[i+1\]变量，所以最大子序和就是比较nums\[i+1\]和local+nums\[i+1\]。(这一点，和上面链接中的文章中说的不太一样，但是我觉得这样理解会更容易一点)

反思：刚开始看到这题，脑子里还是挥不去使用多重for循环暴力求解。在提交之后，看到了用时最长的实现就是暴力求解用时120+ms。而分治法程序跑到了10ms以内。好的算法对于性能的提升竟然恐怖如斯...

[70]: /images/20220511/617123cff7b54e52bab2b32fa1adf057.png
[https_blog.csdn.net_linhuanmars_article_details_21314059]: https://blog.csdn.net/linhuanmars/article/details/21314059
[https_blog.csdn.net_Pwiling_article_details_49405163]: https://blog.csdn.net/Pwiling/article/details/49405163
[70 1]: /images/20220511/11a5129ced3c463ab548cdd6383cd894.png