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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!