LeetCode_53_Maximum Subarray_最大子序和

dafengkuang lv.1

发布时间：2023-02-02 20:22:55 235

相关标签：

题目描述：给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例：

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

此题采用穷举法，枚举左端到右端，需要O(n2)的时间复杂度，然后进行加和的计算，总共需要O(n3)的时间复杂度，这显然是难以接受的。此时想到动态规划来解决问题。
动态规划思想：令数组dp[i]表示以num[i]为结尾元素的连续最大子序列和。通过设置这样一个dp[]数组，最后要求的就是dp[]中最大的元素。因为dp[i]要求必须以num[i]为结尾元素，所以dp[i]只有两种取值情况：1.只包含一个元素，即num[i]自身；2.包含多个元素即dp[i]=dp[i-1]+num[i]，我们要做的只需要将两种情况中最大的值赋值给dp[i]即可，即dp[i]=max(num[i],dp[i-1]+num[i])。这个算法的边界是dp[0]=num[0]，然后就可以依次计算后面的dp[i]的值了。

代码实现：

class Solution {
public:
    int maxSubArray(vector& nums) {
        int length=nums.size();
        int dp[length];
        dp[0]=nums[0];//边界
        for(int i=1;i<length;i++){
            dp[i]=max(nums[i],dp[i-1]+nums[i]);
        }
        int k=0;
        for(int i=1;i<length;i++){
            if(dp[i]>dp[k])
                k=i;
        }
        return dp[k];
    }
};

运行时间：

LeetCode_53_Maximum Subarray_最大子序和_子数组

文章来源： https://blog.51cto.com/u_15855860/5812158

特别声明：以上内容（图片及文字）均为互联网收集或者用户上传发布，本站仅提供信息存储服务！如有侵权或有涉及法律问题请联系我们。