本文主要是介绍面试or笔试3——最大连续子序列和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1 题目及要求
1.1 题目描述
给定k个整数的序列{N1,N2,...,Nk }，其任意连续子序列可表示为{ Ni, Ni+1, ..., Nj }，其中 1 <= i <= j <= k。最大连续子序列是所有连续子序中元素和最大的一个，例如给定序列{ -2, 11, -4, 13, -5, -2 }，其最大连续子序列为{11,-4,13}，最大连续子序列和即为20。如果所有整数均为负数，则最大子序列和为0。
解题思路：
运用动态规划的思想：MaxSum[i] = Max{ MaxSum[i-1] + A[i], A[i]}
2 解答
2.1 代码
#include<iostream>
#include<vector>
#include<assert.h>using namespace std;int max_subSet(vector<int> &v){ //O(n),动态规划int n=v.size();assert(n>0);int currentSum=0,maxSum=0;for(int i=0;i<n;++i){currentSum+=v[i];if(currentSum>maxSum) maxSum=currentSum;else if(currentSum<0) currentSum=0;}return maxSum;
}int main(){vector<int> v={-2, 11, -4, 13, -5, -2};cout<<max_subSet(v)<<endl;return 0;
}这篇关于面试or笔试3——最大连续子序列和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
