最大字段求和

2021/10/9 23:42:52

本文主要是介绍最大字段求和,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

算法1:三重循环暴力求解法

#include <stdio.h>
int maximum_segment_sum(int array[],int n)
{
    int this_sum = 0;
    int max_sum = 0;
    int i,j,k;
    for(i = 0;i < n;i++)
    {//分别以第一个第二个元素开始
        for(j = i;j < n;j++)
        {//不停的在这个串上多加几个元素
            this_sum = 0;
            for(k = i;k <= j;k++)
            {//遍历求和
                this_sum += array[k];
            }
            if(this_sum > max_sum)
            {
                max_sum = this_sum;
            }
        }
    }
    return max_sum;
}
int main() {
    int array[7] = {1,-5,3,4,-2,-3,10};
    int result = 0;
    result = maximum_segment_sum(array,7);
    printf("%d",result);
    return 0;
}

算法2:二重循环求解

#include <stdio.h>
int maximum_segment_sum(int array[],int n)
{
    int this_sum = 0;
    int max_sum = 0;
    int i,j,k;
    for(i = 0;i < n;i++)
    {
        this_sum = 0;
        for(j = i;j < n;j++)
        {
            this_sum += array[j];

            if(this_sum > max_sum)
            {
                max_sum = this_sum;
            }
        }

    }
    return max_sum;
}
int main() {
    int array[7] = {1,-5,3,4,-2,-3,10};
    int result = 0;
    result = maximum_segment_sum(array,7);
    printf("%d",result);
    return 0;
}

算法3:分治法



这篇关于最大字段求和的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程