题目描述
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1]
输出：1
示例 3：
输入：nums = [5,4,-1,7,8]
输出：23
☞动态规划解法
C语言版
/*动态规划 O(n)*/ int maxSubArray(int* nums, int numsSize) { int i = 0; int maxSum = nums[0]; int* dp = (int*)malloc(numsSize * sizeof(int)); *dp = nums[0]; for (i = 1; i < numsSize; i++) { int temp = *(dp + i - 1) + nums[i]; if (temp > nums[i]) { *(dp + i) = temp; } else { *(dp + i) = nums[i]; } if (*(dp + i) > maxSum) { maxSum = *(dp + i); } } free(dp); return maxSum; }
C++版
/*动态规划 O(n)*/ class Solution { public: int maxSubArray(vector<int>& nums) { vector<int> dp(nums.size()); int maxSub = nums[0]; dp[0] = nums[0]; for (int i = 1; i < nums.size(); i++) { dp[i] = max((dp[i - 1]) + nums[i], nums[i]); //子序列和与当前值，取大值 maxSub = max(maxSub, dp[i]); //更新最大值标记 } return maxSub; } };
Python版
#动态规划 class Solution: def maxSubArray(self, nums: List[int]) -> int: #返回值int，参数nums类型为int dp = [] maxFlag = nums[0] dp.append(nums[0]) for i in range(1, len(nums)): dp.append(max(dp[i - 1] + nums[i], nums[i])) maxFlag = max(maxFlag, dp[i]) return maxFlag
☞贪心策略版
C语言版
/*贪心策略 时间复杂度 O(n)*/ int maxSubArray(int* nums, int numsSize) { int i = 0; int maxSum = nums[0]; int numSum = 0; for (i = 0; i < numsSize; i++) { numSum = numSum + nums[i]; if (maxSum < numSum) { maxSum = numSum; } if (numSum < 0) { numSum = 0; } }
C++版
/*贪心算法 O(n)*/ class Solution { public: int maxSubArray(vector<int>& nums) { int maxNum = nums[0]; int subSum = 0; for (int i = 0; i < nums.size(); i++) { subSum = subSum + nums[i]; if (subSum > maxNum) { maxNum = subSum; //如果累加和大于0就一直累加，并更新最大值 } if (subSum < 0) { subSum = 0; //一旦累加和变成小于0，就抛弃这个负数，从0开始重新累加，保留原来的最大值 } } return maxNum; } };
Python版
#贪心 class Solution: def maxSubArray(self, nums: List[int]) -> int: #返回值int，参数nums类型为int subSum = 0 maxSum = nums[0] for i in range(len(nums)): subSum = subSum + nums[i] maxSum = max(maxSum, subSum) if subSum < 0: subSum = 0 return maxSum
