[剑指Offer]42-连续子数组的最大和(DP)
2024-09-27 07:42:07
题目链接
题意
例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和(子向量的长度至少是1).
解题思路
思路一 O(n)：
从前向后遍历，若和为负值，则更新起点；若和为正值，当出现比当前 记录和最大值变量中的最大值 大时，则更新变量。
思路二，动态规划的思路（与思路一思想一致，实现方式不同） O(n)：
max[I]记录从头扫到i位置元素为止和最大值。
状态转移方程：max[i]=max[i-1]+val[i]，当max[i-1]>0;max[i]=val[I]，当max[i-1]<0。
思路一代码(Java)
class Solution {
public int maxSubArray(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int sum = 0;
int max = Integer.MIN_VALUE;
for (int num : nums) {
sum += num;
if (sum > max) {
max = sum;
}
if (sum < 0) {
sum = 0;
}
}
return max;
}
}
思路二代码(C++)
class Solution {
public:
int FindGreatestSumOfSubArray(vector<int> array) {
vector<int> sum;
for(int i=0;i<array.size();++i){
if(i==0){
sum.push_back(array[i]);
}
else{
if(sum[i-1]<=0){
sum.push_back(array[i]);
}
else{
sum.push_back(sum[i-1]+array[i]);
}
}
}
int maxSum;
for(auto it=sum.begin();it!=sum.end();++it){
if(it==sum.begin()){
maxSum=*it;
}
else{
if(*it>maxSum){
maxSum=*it;
}
}
}
return maxSum;
}
};
最新文章
- Dos命令查看端口占用及关闭进程
- C# 获得MP4时长
- VI小技巧
- Android 自定义控件-TextView
- HDU-5504(逻辑if-else大水题)
- ios的自动转屏
- IOS开发之XCode学习012：Slider和ProgressView
- 从线性模型（linear model）衍生出的机器学习分类器（classifier）
- 杭电ACM2005--第几天？
- insert into select的实际用法
- C# File API
- git安装包解压后没有configure
- 九、Brideg 桥接模式
- Spring.net(二)----初探IOC容器
- vim多行注释和取消注释 Ubuntu
- java基础6 面向对象的详解
- Laravel5.1 搭建博客 --文章的增删改查
- Python小知识点（2）
- swiper 、css3制作移动端网站，折叠导航
- 队列 和 堆栈用python 来实现