作者:翟天保Steven 题目描述:输入一个长度为n的整型数组array,数组中的一个或连续多个整数组成一个子数组,子数组最小长度为1。求所有子数组的和的最大值。 数据范围: 1<=n<=2×105 0<=a[i]<=100 要求:时间复杂度为 O(n),空间复杂度为 O(n) 进阶:时间复杂度为 O(n),空间复杂度为 O(1) 示例:输入: [1,-2,3,10,-4,7,2,-5] 返回值: 18 说明: 经分析可知,输入数组的子数组[3,10,-4,7,2]可以求得最大和为18 解题思路:本题考察算法-动态规划算法的使用。用两种动态规划的解法。 解法一:使用常规的动态规划思路:用一个vector-dp存储到各个下标时的最大连续子数组和,进行一轮遍历,若dp[i-1]+array[i]比array[i]大,说明到前一下标为止的最大连续子数组,可以把当前下标纳入到该连续子数组中;反之,则以array[i]为新的起点,继续向后扩展连续子数组;与此同时,动态刷新最大值maxsum。 解法二:对空间复杂度进行优化:常规解法使用vector来记录各个下标的最大连续子数组和,但本题目的要求并没有需要读取vector中信息,因此该vector可以优化掉。用x代替dp[i-1],相当于当前下标前的最大连续子数组和,其他的同解法一一致,这样vector的空间就节省下来了。 测试代码:解法一:动态规划
解法二:动态规划进阶
|
|