LeetCode[53]最大子数组和

2024-01-07 17:45:50
  • Description:

给你一个整数数组?nums?,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

子数组?是数组中的一个连续部分。

  • 解法1:遍历--超时,内存超限,不通过,算法复杂度O(n^3)了吧
int sum(vector<int>& v, int begin, int num)
    {
        int s = 0;
        for(int i = 0; i < num; i++)
            s += v[begin+i];
        return s;
    }
    int maxSubArray(vector<int>& nums) {
        
        int max = nums[0], n = 1;
        int size = nums.size();
        if(size == 1)
            return nums[0];
        while(n <= size)
        {
            for(int i = 0; i + n <= size; i++)
            {                
                int s = sum(nums, i, n);
                if(s > max)
                    max = s;
            }
            n++;
        }
        return max;
    }
  • 解法2:动态规划

这里有个关键状态转移方程的定义,dp[i] = max(nums[i], nums[i]+dp[i-1],在这道题里了解到了算法里的无后效性,dp[i]表示以nums中第i个元素结尾的和最大的字符串,所以dp[i]分为两种情况,一种是nums[i]单独一个元素成为字符串,或者加上前边的第[i-1]个元素形成的字符串,即nums[i]+dp[i-1],两者中取最大的即为dp[i]=max(nums[i], nums[i]+dp[i-1])

int maxSubArray(vector<int>& nums) {
        int size = nums.size();
        vector<int> dp(size);
        dp[0] = nums[0];
        for(int i = 1; i < size; i++)
            dp[i] = max(nums[i], nums[i] + dp[i-1]);
        int res = dp[0];
        for(int i = 0; i < size; i++)
            res = max(res, dp[i]);
        return res;
    }

文章来源:https://blog.csdn.net/weixin_44872774/article/details/135402945
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。