/* * @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数组中存放的数都变成了各个阶段所求得的最大值，最后返回这些数的最大值即可。