最大子段和

最大子段和:给出一个数组,计算其中连续的最大的子段和

运行代码,及运行思想:

/**
 * 动态规划:计算最大子段和
 * 算法描述:
 * 数组a 有n个元素, 记 s[i] 为从a【0】到a[i]中,包含a[i]的最大子段和
 * 则: s[i] 的值为:  s[i-1]>0时, s[i-1]+a[i]
 *                     否则 a[i]
 */
#include <stdio.h>
#include <stdlib.h>
int maxSub(int *a, int n)
{
    int i=0, max=0, max_pos = 0;
    int si_1=0, si = 0;//分别记录s[i-1], 和 s[i]的值
    int *p = (int *)malloc(n*sizeof(int)); //p[i] 助于记录哪些单元被选择, p[i]=1 表示s[i]计算的结果中中使用了s[i-1]的值
    
    if (p==NULL)
        return -1;
    max = si_1 = a[0];
    p[0] = 0;
    for (i=1; i<n; i++)
    {
        if (si_1<0)
        {
            p[i] = 0;
            si = a[i];
        } 
        else
        {
            p[i] = 1;
            si = si_1+a[i];
        }
        si_1 = si;
        if (si>max)
        {
            max = si;
            max_pos = i;
        }
    }

    //找到最大子段和的位置
    for (i=max_pos; i>=0; i--)
        if (p[i]==0)
            break;

    //即i..max_pos为最大子段和的元素
    printf("%d--%d:%d\n", i, max_pos, max);

    free(p);
    p = NULL;
    return max;
}

int main()
{
    int n = 10;
    int a[10] = {3, 5, 6, 10, -2, -5, 3, 5, -112, -324};

    maxSub(a, n);

    return 0;
}

源代码摘自:http://blog.csdn.net/chaoyue1216/article/details/6870339

运行结果:

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Android-薛之涛

Android Parcelable

      Paracelable是android自己的实现序列化的接口,是anroid推荐使用的.那么什么事序列化呢?简单来说就是将对象转换为可以传输的二进制...

913
来自专栏佳爷的后花媛

java基础知识

Vector、Stack、HashTable、ConcurrentHashMap、Properties

2775
来自专栏数据科学

redis流计算

使用了tornado的异步和streamz的流处理两个库,需要redis 5.0以上版本

1934
来自专栏木木玲

JVM中 对象的内存布局 以及 实例分析

2078
来自专栏偏前端工程师的驿站

意译:《JVM Internals》

译者语                                  为加深对JVM的了解和日后查阅时更方便,于是对原文进行翻译。内容是建立在我对JVM的认...

2367
来自专栏Golang语言社区

Go Channel 应用模式(二)

eapache/channels提供了一些channel应用模式的方法,比如上面的扇入扇出模式等。

1493
来自专栏醉梦轩

Python中动态创建类的方法

在Python中,类也是作为一种对象存在的,因此可以在运行时动态创建类,这也是Python灵活性的一种体现。

2633
来自专栏章鱼的慢慢技术路

字符串练习——输入关键字找歌曲

1665
来自专栏IMWeb前端团队

Zepto核心模块之工具方法拾遗

本文作者:IMWeb 谦龙 原文出处:IMWeb社区 未经同意,禁止转载 前言 平时开发过程中经常会用类似each、map、forEach之类的方法...

2936
来自专栏前端知识分享

第63天:json的两种声明方式

1、 对象声明 var  json = {width:100,height:100}

1372

扫码关注云+社区

领取腾讯云代金券