53. Maximum Subarray(动态规划)
2024-10-21 03:02:31
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.
分析:
创建了dp数组,dp[i]表示以array[i]结尾的最大子数组和为dp[i],动态转移方程为dp[i]=max(dp[i-1]+array[i],array[i]);
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int dp[nums.size()]={0};
dp[0]=nums[0];
int maxsum=nums[0];
for(int i=1;i<nums.size();i++){
dp[i]=max(dp[i-1]+nums[i],nums[i]);
maxsum=max(maxsum,dp[i]);
}
return maxsum;
}
};
最新文章
- python学习6 web开发
- Moneybookers API支付方式开发 步骤
- 配置springmvc在其他类中(spring容器外)获取注入bean
- linux--杂记(rework)
- iOS 杂笔-20(UIView和CALayer的区别与联系)
- Sqlserver中存储过程,触发器,自定义函数(一)
- [转贴]C++开源库
- Unity SendMessage方法
- Jquery mobile中用Jquery的append()追加的内容没有Jquery mobile的样式
- IDEA 创建Web项目
- 《剑指offer》 反转链表
- ubuntu使任何地方右键都能打开terminal
- Django2.0资料
- CodeForces - 669D
- 《Redis 数据操作》
- linux----------wdcp(是一款集成的linux环境)中的各种坑。
- jquery.validate使用详解
- GO入门——2. 变量
- 《学习R》
- MySQL索引的维护与优化——查找重复及冗余索引