定（可能有负数）整数序列A1, A2, A3..., An，求这个序列中子序列和的最大值。（为方便起见，如果所有整数均为负数，则最大子序列和为0）。
可以参考我的：https://blog.csdn.net/qq_33957603/article/details/80554648
以及代码提交（验证正确）地址：http://www.joyoi.cn/problem/tyvj-1305
###传统的做法是，枚举(只要对的话就够了
如果n<=10^3，我们很容易写出枚举（s是前缀和，区间[l,r]的和就是s[r]-s[l-1]。枚举l,r即可。
#include<stdio.h>
#define maxn 300010
#define max(a,b) (a>b?a:b)
int a[maxn], q[maxn];
long long s[maxn], ans;
int main(){
int n, m;
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i++){
scanf("%d",&a[i]); s[i]=s[i-1]+a[i];
}
for(int i = 1; i <= m; i++)//枚举长度
for(int j = i; j <= n; j++)//枚举r
ans = max(ans, s[j]-s[j-i]);//可以算出l
printf("%d\n",ans);
return 0;
}
###如果需要更快的，，，可以考虑用单调队列
#include<stdio.h>
#define max(a,b) (a>b?a:b)
#define maxn 300010
using namespace std;
int a[maxn], q[maxn];
long long s[maxn], ans;
int main(){
int n, m;
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i++){
scanf("%d",&a[i]); s[i]=s[i-1]+a[i];
}
int l = 1, r = 1;
q[l] = 0; //save j
for(int i = 1; i <= n; i++){
while(l<=r && q[l]<i-m)l++;
ans = max(ans, s[i]-s[q[l]]);
while(l<=r && s[q[r]]>s[i])r--;
q[++r] = i;
}
printf("%d\n",ans);
return 0;
}
include 'stdio.h'
int max(int *a){
int sum = 0
for(int i = 0;i if(sum sum = 0;
if(a[i]>0){
sum+=a[i];
}
}
return sum;
}
参考这个程序 https://blog.csdn.net/linux_ever/article/details/50464947
c语言只要把输入输出换成scanf printf即可。
int maxSubArray(vector& nums) {
int size=nums.size();
int sum=0;
int max=(-2147483647-1);
for(int i=0;i<size;++i){
sum+=nums[i];
if(max<sum){
max=sum;
}
if(sum<0){
sum=0;
}
}
return max;
}
include 'stdio.h'
int max(int *a){
int sum = 0
for(int i = 0;i if(sum sum = 0;
if(a[i]>0){
sum+=a[i];
}
}
return sum;
}
https://blog.csdn.net/linux_ever/article/details/50464947
int MaxSubsequenceSum( const int A[],int N)
{
int ThisSum,MaxSum,i;
ThisSum=0;
MaxSum=0;
for(i=0;i ThisSum+=A[i];
if(ThisSum>MaxSum){
MaxSum=ThuisSum;
}else if(ThisSum<0){
ThisSum=0;}}
retu}rn Maxsum;
方法有很多，效率比较高的是分治法（O(nlogn)）和动态规划法（O(n)）。
动态规划法：
int MaxSum(int *arr, int n)
{
int sum = 0, b = 0;
for (int i = 0; i < n; i++)
{
if (b > 0)
b += arr[i];
else
b = arr[i];
if (b > sum)
sum = b;
}
return sum;
}
#include
#include
long seriesMaxSum(int *series, size_t n);
void main(size_t argc, char **argv) {
if (argc > 1) {
int *series;
size_t counter;
if (!(series = malloc((argc - 1) * sizeof(int)))) {
fprintf(stderr, "Out of memory...\n");
return;
}
for (counter = 1; counter < argc; counter++)
*(series + (counter - 1)) = atoi(argv[counter]);
printf("The biggest sum in the series is: %ld\n", seriesMaxSum(series, argc - 1));
} else
printf("<Usage>: ./%20s [series]\nExample: ./%20s (\\d+\\s)+\n", argv[0], argv[0]);
}
long seriesMaxSum(int *series, size_t n) {
long partialSum = 0, biggestSum = 0;
size_t index;
for (index = 0; index < n; index++) {
if ((partialSum + series[index]) >= partialSum) {
if ((partialSum += series[index]) >= biggestSum)
biggestSum = partialSum;
} else
partialSum = 0;
}
return biggestSum;
}
1.1 分解：这个数组只能出现在三个位置：从中间分，要么完全在左边，要么完全在右边，要么穿过中间，所以分三部分求最大
1.2 求解：如果在左边或右边继续分，最后只剩一个数返回，对于穿过中间的，分成两部分求最大，每次都如此。
1.3 组合：每次返回左边，右边，中间这三个中最大的
class Solution {
public int maxSubArray(int[] nums) {
return findMax(nums,0,nums.length-1);
}
public static int findMax(int []num,int left,int right){
if (left>=right)return num[left];
int mid=(left+right)/2;
//寻找左边最大
int lmax=findMax(num,left,mid-1);
//寻找右边最大
int rmax=findMax(num,mid+1,right);
//寻找中间最大，并分成两部分，找从中间左边连续最大，中间到右边连续最大，最后加起来
int mmax=num[mid],t=mmax;
for (int i=mid-1;i>=left;i--){
t+=num[i];
mmax=Math.max(mmax,t);
}
t=mmax;
for (int i=mid+1; i<=right; i++){
t+=num[i];
mmax=Math.max(mmax,t);
}
//合并
return Math.max(mmax,Math.max(lmax,rmax));
}
}
求最大的子序列和问题
给定整数A1,A2,....An，....（可能有负数）,求该数据序列的最大子序列的和。
比如：输入-2， 11， -4， 13， -5， -2； 答案是20(11，-4，13三个连续数字的和)
我们遍历一次数据序列，当每次的this_sum大于最大值的时候就更新max_sum的值。当this_sum小于0的时候，就把它置为0，再从当前位置开始计算（每次求和的结果小于0，就从下一个数据开始求和）。还有一点要清楚，最大序列的第一个数字不可能小于0。可以看出该算法的时间复杂度是O(n)；
该问题还有其它几种时间复杂度比较高的算法。具体看：数据结构与算法分析C++描述（2.3章节）
[cpp] view plain copy
/*************************************************************************
> File Name: max_seq_sum.cpp
> Author:
> Mail:
> Created Time: 2016年01月05日 星期二 19时49分30秒
************************************************************************/
#include
#include
using namespace std;
void input_data(vector & data)
{
int tmp;
cout << "输入数据序列：" << endl;
while(cin >> tmp){
data.push_back(tmp);
}
}
void output_data(vector & data)
{
cout << "输入的数据序列：" << endl;
for (int i = 0; i < data.size(); ++i)
cout << data[i] << " ";
cout << endl;
}
int max_seq_sum(vector & data)
{
int max_sum = 0, this_sum = 0;
for (int i = 0; i < data.size(); ++i){
this_sum += data[i];
if(this_sum > max_sum)
max_sum = this_sum;
else if(this_sum < 0)
this_sum = 0;
}
return max_sum;
}
int main()
{
vector data;
//输入数据
input_data(data);
output_data(data);
cout << "最大序列的值是: ";
cout << max_seq_sum(data) << endl;
return 0;
}
int main(void)
{
int n, a[100001];
while (~ scanf("%d", &n))
{
int i;
for (i = 1; i <= n; i ++)
scanf("%d", &a[i]);
int sum = a[1], min = a[1]; // 初始值
for (i =2; i <= n; i ++)
{
if (sum <= 0)
sum = a[i]; // 如果前面位置最大连续子序列和小于0, 就讲此时的位置的值记录下来
else
sum += a[i]; // 如果大于0, 就继续相加。
if (sum > min)
min = sum;
}
printf("%d\n", min);
}
return 0;
}
这个如果输入的是
5
-1 -2 -3 -4 -5
输出的是-1
你可以加一个循环判断 如果都是负的话 输出0即可
另外命名一个数组b[n],当An为正数计入b[n]，因为为负数时2求和值会变小，所以只累计大于0的数，只需要将b[n]求和就可以了。
#include 'stdio.h'
int Max(int n, int *b)
{
int m=0, sum=0;//设m为求和中间变量
int i;
for(i=0; i {
if (m>0)
m+=b[i];
else
m=b[i];
if(m>=sum)
sum=m;
else
sum=0;
}
return sum;
}