当前位置:  编程技术>c/c++/嵌入式

求子数组最大和的实例代码

    来源: 互联网  发布时间:2014-10-12

    本文导语:  题目:输入一个整形数组,数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。 例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大...

题目:
输入一个整形数组,数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为O(n)。

例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2,
因此输出为该子数组的和18。

找到状态转移方程,dp[i]表示前i个数中,包含i的子数组的最大和。要么第i个数自己最大,要么他要和包含i-1的子数组最大和(即dp[i-1])联合在一起.
即dp[i] = max{arr[i],dp[i-1]+arr[i]};

代码如下;

代码如下:

#include
#define max(a,b) (a)>(b)?(a):(b)

int res(int* arr, int len){
    //学到一个定义最小数的方法:)
    int max = -(1


    
 
 

您可能感兴趣的文章:

  • 求子数组最大和的解决方法详解
  •  
    本站(WWW.)旨在分享和传播互联网科技相关的资讯和技术,将尽最大努力为读者提供更好的信息聚合和浏览方式。
    本站(WWW.)站内文章除注明原创外,均为转载、整理或搜集自网络。欢迎任何形式的转载,转载请注明出处。












  • 相关文章推荐




  • 特别声明:169IT网站部分信息来自互联网,如果侵犯您的权利,请及时告知,本站将立即删除!

    ©2012-2021,,E-mail:www_#163.com(请将#改为@)

    浙ICP备11055608号-3