- /*
- * @lc App=leetcode.cn id=53 lang=c
- *
- * [53] 最大子序和
- *
- * https://leetcode-cn.com/problems/maximum-subarray/description/
- *
- * algorithms
- * Easy (42.92%)
- * Total Accepted: 39.9K
- * Total Submissions: 93K
- * Testcase Example: '[-2,1,-3,4,-1,2,1,-5,4]'
- *
- * 给定一个整数数组 nums , 找到一个具有最大和的连续子数组 (子数组最少包含一个元素), 返回其最大和.
- *
- * 示例:
- *
- * 输入: [-2,1,-3,4,-1,2,1,-5,4],
- * 输出: 6
- * 解释: 连续子数组 [4,-1,2,1] 的和最大, 为 6.
- * [-2,1]
- * [1,2]
- *
- * 进阶:
- *
- * 如果你已经实现复杂度为 O(n) 的解法, 尝试使用更为精妙的分治法求解.
- *
- */
- int maxSubArray(int* nums, int numsSize) {
- if(numsSize==1){
- return nums[0];
- }
- int i=0,j=0,max=-32767,sum;
- for(i=0;i<numsSize;i++){
- sum=nums[i];
- j=i+1;
- while(j<numsSize){
- sum+=nums[j];
- if(sum>max){
- max=sum;
- }
- j++;
- }
- }
- for(i=0;i<numsSize;i++){
- if(nums[i]>max){
- max = nums[i];
- }
- }
- return max;
- }
这是自己的傻屌代码... 运行效率及其差.
核心思想就是, 先进行两层循环, 然后逐一的比较大小赋予 max 新的值.
然后再进行一轮循环, 找出是否有单个值就大于 max 的值, 有的话赋予 max 新的值.
所以时间复杂度达到了 O(n²+n)
这道题真正的解法应该是用动态规划的方法:
设 sum[i] 为以第 i 个元素结尾且和最大的连续子数组. 假设对于元素 i, 所有以它前面的元素结尾的子数组的长度都已经求得, 那么以第 i 个元素结尾且和最大的连续子数组实际上, 要么是以第 i-1 个元素结尾且和最大的连续子数组加上这个元素, 要么是只包含第 i 个元素, 即 sum[i]
= max(sum[i-1] + a[i], a[i]). 可以通过判断 sum[i-1] + a[i] 是否大于 a[i] 来做选择, 而这实际上等价于判断 sum[i-1] 是否大于 0. 由于每次运算只需要前一次的结果, 因此并不需要像普通的动态规划那样保留之前所有的计算结果, 只需要保留上一次的即可, 因此算法的时间和空间复杂度都很小
- /*
- * @lc App=leetcode.cn id=53 lang=c
- *
- * [53] 最大子序和
- *
- * https://leetcode-cn.com/problems/maximum-subarray/description/
- *
- * algorithms
- * Easy (42.92%)
- * Total Accepted: 39.9K
- * Total Submissions: 93K
- * Testcase Example: '[-2,1,-3,4,-1,2,1,-5,4]'
- *
- * 给定一个整数数组 nums , 找到一个具有最大和的连续子数组 (子数组最少包含一个元素), 返回其最大和.
- *
- * 示例:
- *
- * 输入: [-2,1,-3,4,-1,2,1,-5,4],
- * 输出: 6
- * 解释: 连续子数组 [4,-1,2,1] 的和最大, 为 6.
- * [-2,1]
- * [1,2]
- *
- * 进阶:
- *
- * 如果你已经实现复杂度为 O(n) 的解法, 尝试使用更为精妙的分治法求解.
- *
- */
- int maxSubArray(int* nums, int numsSize) {
- int sum=0,max=nums[0];
- for(int i=0;i<numsSize;i++)
- {
- if(sum>0)
- sum+=nums[i];
- else
- sum=nums[i];
- if(sum>max)
- max=sum;
- }
- return max;
- }
- ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
pyhon 则可以相对简单些:
- #
- # @lc App=leetcode.cn id=53 lang=python3
- #
- # [53] 最大子序和
- #
- # https://leetcode-cn.com/problems/maximum-subarray/description/
- #
- # algorithms
- # Easy (42.92%)
- # Total Accepted: 39.9K
- # Total Submissions: 93K
- # Testcase Example: '[-2,1,-3,4,-1,2,1,-5,4]'
- #
- # 给定一个整数数组 nums , 找到一个具有最大和的连续子数组 (子数组最少包含一个元素), 返回其最大和.
- #
- # 示例:
- #
- # 输入: [-2,1,-3,4,-1,2,1,-5,4],
- # 输出: 6
- # 解释: 连续子数组 [4,-1,2,1] 的和最大, 为 6.
- #
- #
- # 进阶:
- #
- # 如果你已经实现复杂度为 O(n) 的解法, 尝试使用更为精妙的分治法求解.
- #
- #
- class Solution:
- def maxSubArray(self, nums: List[int]) -> int:
- length = len(nums)
- for i in range(1,length):
- Max = max(nums[i]+nums[i-1],nums[i])
- nums[i]=Max
- return max(nums)
这里在数组的循环中, 当前值与前面的值得和进行比较, 较大的存放到当前的 nums 数组中.
最后 nums 数组中存放的数都变成了各个阶段所求得的最大值, 最后返回这些数的最大值即可.
来源: http://www.bubuko.com/infodetail-2983565.html