C语言穷举解决最大子序列含测试

题目再现

设给定一个整数序列 a 1 , a 2 , . . . , a n a_1,a_2,...,a_n a1​,a2​,...,an​(其可能有负数),设计一个穷举算法, ∑ n = 1 j a k \sum\limits_{n=1}^j{a_k} n=1∑j​ak​的最大值，例如对于序列A={1,-1,1,-1,-1,1,1,1,1,1,-1,-1,1,-1,1,-1},子序列 A [ 5..9 ] = 1 , 1 , 1 , 1 , 1 A[5..9]={1,1,1,1,1} A[5..9]=1,1,1,1,1具有最大值5.

输入输出及测试效果

题目讲解

设i和j都是序列中元素的序号(称为下标),若从序列中某个元素起连续提取若干元素组成的序列，即为原序列的子序列。算法尝试从每个i(初始为0)起，用j连续累加1个、2个，。。。，记下累加值中最大的，以及相应的i、j值，算法结束，即得所需结果。设用数组a[n]存放序列, a i a_i ai​存储于a[i-1]内

题目源码

#include<stdio.h>
#define maxsize 6
int maxSubsequence(int a[], int n,int *i,int *j) {
    //算法返回最大子序列的值，并通过引用参数i和j返回起止运算下标
    int sum,maxSum,id,jd,k;
    maxSum = 0;
    *i = 0;
    *j = 0;
    for(id = 0;id<n;id++) {
        for(jd = id;jd<n;jd++) {
            sum = 0;
            for(k = id;k<=jd;k++)
                sum += a[k];
            if(sum > maxSum) {
                maxSum = sum;
                *i = id;
                *j = jd;
            }
        }

    }
    return maxSum;
}

int main(){
    int A[maxsize] ;
    for(int i =0;i<maxsize;i++)
        scanf("%d",&A[i]);
    int n = sizeof(A)/sizeof(int);
    int x,y,z;
    printf("输入序列为: ");
    for(int i = 0;i<n;i++)
        printf("%d ",A[i]);
    printf("\n");
    x = maxSubsequence(A,n,&y,&z);
    printf("累加和为%d,区间从%d到%d",x,y,z);
    return 0;
}

源码跑路

假如我们输入的是-1 1 2
一共3个长度，传入的函数参数如下

• A：数组元素首地址
• n 数组长度
• y 区间下限的地址传入
• z 区间上限的地址传入

maxSubsequence是一个穷举算法，所以我们按照传统的方法进行演示代码结果
返回结果maxsum置为0，i和j置成0

id = 0

• jd = 0 sum = 0 k = 0k<= 0 maxsum = 0
• jd =1 sum = 0 k = 0 k <= 1 maxsum = 0
• jd =2 sum = 0 k=0 k<=2 maxsum = 2

id = 1

• jd = 1 sum = 0 k = 1 k<= jd maxsum =1
• jd = 2 sum = 0 k=1 k<= 2 maxsum = 3

id = 2

• jd = 2 sum = 0 k=2 k<= jd sum = 2 < maxsum =3

id = 3 不满足 直接刷出maxsum

maxsum=3

参考文献

殷人昆著.数据结构与算法解析.北京：清华大学出版社，2021.4