LeetCode 53. 最大子数组和 （动态规划+贪心——C/C++/Python）

欢迎加入【Linux C/C++/Python社区】一起探讨和分享Linux C/C++/Python/Shell编程、机器人技术、机器学习、机器视觉、嵌入式AI相关领域的知识和技术。

---

53. 最大子数组和

---

关注专栏《算法题LeetCode》，高效刷题，本专栏使用C./C++/Python三种语言，多种解法刷题，题目来源为力扣。

题目描述

给你一个整数数组 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)*/intmaxSubArray(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版

#动态规划classSolution:defmaxSubArray(self, nums: List[int])->int:#返回值int，参数nums类型为int
        dp =[]
        maxFlag = nums[0]
        dp.append(nums[0])for i inrange(1,len(nums)):
            dp.append(max(dp[i -1]+ nums[i], nums[i]))
            maxFlag =max(maxFlag, dp[i])return maxFlag

☞贪心策略版

C语言版

/*贪心策略  时间复杂度 O(n)*/intmaxSubArray(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;}}return maxSum;}

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版

#贪心classSolution:defmaxSubArray(self, nums: List[int])->int:#返回值int，参数nums类型为int
        subSum =0
        maxSum = nums[0]for i inrange(len(nums)):
            subSum = subSum + nums[i]
            maxSum =max(maxSum, subSum)if subSum <0:
                subSum =0return maxSum