题目:给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
子数组是数组中的一个连续部分。
解法一:贪心算法
解法二:分治算法
本题解法及感悟:这道题我运用了两种解法分别求解,第一种是贪心算法,它的核心是每一步只做当前局部最优选择,希望最终得到全局最优解,在此题中只需要一次遍历就可以,代码简短,运行速度快,时空复杂度小;第二种是分治算法,它的核心是把数组对半拆分,递归求解,本题有左区间、右区间、跨中间区间三种,相对第一种方法来说代码较长,时空复杂度都比较大,但是也很容易理解。
通过对比两种算法,我看到了两个算法的优劣,也会恰当地选择、正确的应用,降低时空复杂度,提高代码的可行性