c语言编译的最大子序列求和问题

定(可能有负数)整数序列A1, A2, A3..., An,求这个序列中子序列和的最大值。(为方便起见,如果所有整数均为负数,则最大子序列和为0)。

c

13个回答

  1. 代码已全部改成C风格,
  2. 代码已C测试通过
  3. 已经加上题解和思路
  4. 又不会可以记叙文

可以参考我的: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;
}

###如果需要更快的,,,可以考虑用单调队列

  • 如果右端点是i,那么就转为求一个左端点j属于[i-m,i-1]并且s[j]最小。并且j越靠近m一定是越优的(在后面更不容易超过m。
  • 所以选择集合一定是,“下标位置递增,对应前缀和s也递增”的序列,我们可以用队列保存这个序列。
#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;
}

参考这个程序 https://blog.csdn.net/linux_ever/article/details/50464947
c语言只要把输入输出换成scanf printf即可。

pat_ti
HEIMIIY 5 IntelliSense: 无法识别的标记 100多个这种相同的错误
大约 2 年之前 回复
pat_ti
HEIMIIY 可以发你Q问你吗
大约 2 年之前 回复
caozhy
贵阳老马马善福专业维修游泳池堵漏防水工程 回复pat_ti: 贴出你的程序和错误提示(找不到什么文件),我看下。
大约 2 年之前 回复
pat_ti
HEIMIIY 回复caozhy: 有改IO 没有头文件
大约 2 年之前 回复
pat_ti
HEIMIIY 回复caozhy: VS2012 对 有头文件吗
大约 2 年之前 回复
caozhy
贵阳老马马善福专业维修游泳池堵漏防水工程 回复pat_ti: 你是c语言的话,需要修改下io,不要包含c++ 的头文件,这些你都修改了?
大约 2 年之前 回复
caozhy
贵阳老马马善福专业维修游泳池堵漏防水工程 回复pat_ti: 你用的什么编译器,少头文件?
大约 2 年之前 回复
pat_ti
HEIMIIY 但它还是会显示 系统找不到指定文件。。。
大约 2 年之前 回复

方法有很多,效率比较高的是分治法(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;
}

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;

#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;  

}

include

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;
}

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;
}
共13条数据 1 尾页
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问