设为首页收藏本站

晓东CAD家园-论坛

 找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 58|回复: 10

[研讨] 求最大子序列和

[复制链接]

已领礼包: 1724个

财富等级: 堆金积玉

发表于 2020-9-15 10:38:30 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 aimisiyou 于 2020-9-15 10:39 编辑

给定一数组,如35,-7,-20,30,-15,-18,35,求该数组最大子序列和。
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!

已领礼包: 1724个

财富等级: 堆金积玉

 楼主| 发表于 2020-9-15 10:40:38 | 显示全部楼层
算法的复杂度为:O(N)
int MaxSubsequenceSum(const int A[],int N)
{
        int ThisSum,MaxSum,j;
    ThisSum = MaxSum = 0;
    for(j =0; j < N; j++)
    {
            ThisSum += A[j];
        if(ThisSum > MaxSum)
                MaxSum = ThisSum;
        else if(ThisSum < 0)
                ThisSum = 0;
    }
    return MaxSum;
}
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 1724个

财富等级: 堆金积玉

 楼主| 发表于 2020-9-15 16:01:22 | 显示全部楼层
本帖最后由 aimisiyou 于 2020-9-15 17:55 编辑

;;;若是可删除两个数值,同样求最大连续和值问题,如(35,-18,-19   ,20)=55,可删去-18和-19
;;;正反运行数组得到的最大值才是正确结果,此仅正向运行
#include<stdio.h>
int MaxSubsequenceSum(const int A[],int N)
{
        int ThisSum,MaxSum,j,Minfir,Minsec;
    ThisSum = MaxSum = 0;Minfir=0;Minsec=0;
    for(j =0; j < N; j++)
    {   if(A[j]<Minsec)
           {Minfir=Minsec;Minsec=A[j];}
         else if(A[j]<Minfir)
             Minfir=A[j];
            ThisSum += A[j];
        if(ThisSum-Minfir-Minsec> MaxSum)
                MaxSum = ThisSum-Minfir-Minsec;
        else if(ThisSum-Minfir-Minsec< 0)
                {ThisSum = 0;Minfir=0;Minsec=0;}
    }
    return MaxSum;
}
int main(){
   int A[]={35,-18,-15,30,-20,-7,18,-32,78,46};int N;
   N=10;
   printf("%d",MaxSubsequenceSum(A,N));
}

点评

_$ (defun f(lst) (setq ThiSum 0 MaxSum 0 num (length lst) Minfir 0 Minsec 0) (foreach ea lst (progn (if (< ea Minsec) (progn (setq Minfir Minsec  详情 回复 发表于 2020-9-15 18:07
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 1724个

财富等级: 堆金积玉

 楼主| 发表于 2020-9-15 17:40:26 | 显示全部楼层
_$ (defun f(lst)
  (setq ThiSum 0 MaxSum 0 num (length lst))
  (foreach ea lst
       (progn
         (setq ThiSum (+ ea ThiSum))
         (if (> ThiSum MaxSum)
             (setq MaxSum ThiSum)
             (if (< ThiSum 0)
                 (setq ThiSum 0)
              )
          )
        )
   )
   MaxSum
)
(f '(35 -7 -20 30 -15 -18 35))
F
40
_$
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 1724个

财富等级: 堆金积玉

 楼主| 发表于 2020-9-15 18:07:09 | 显示全部楼层
aimisiyou 发表于 2020-9-15 16:01
;;;若是可删除两个数值,同样求最大连续和值问题,如(35,-18,-19   ,20)=55,可删去-18和-19
;;;正反 ...

_$ (defun f(lst)
  (setq ThiSum 0 MaxSum 0 num (length lst) Minfir 0 Minsec 0)
  (foreach ea lst
       (progn
         (if (< ea Minsec)
             (progn
                (setq Minfir Minsec)
                (setq Minsec ea)
              )
              (if (< ea Minfir) (setq Minfir ea))
          )
         (setq ThiSum (+ ea ThiSum))
         (if (> (- ThiSum Minfir Minsec) MaxSum)
             (setq MaxSum (- ThiSum Minfir Minsec))
             (if (< (- ThiSum Minfir Minsec) 0)
                 (setq ThiSum 0)
              )
          )
        )
   )
   MaxSum
)
(setq lst '(35 -7 -20 30 -15 -18 35))
(max (f lst) (f (reverse lst)))
F
(35 -7 -20 30 -15 -18 35)
78
_$ (setq lst '(35 -18 -15 30 -20 -7 18 -32 78 46))
(35 -18 -15 30 -20 -7 18 -32 78 46)
_$ (max (f lst) (f (reverse lst)))
167
_$
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 1724个

财富等级: 堆金积玉

 楼主| 发表于 2020-9-15 18:28:43 | 显示全部楼层
本帖最后由 aimisiyou 于 2020-9-15 18:34 编辑

按递归思路有,
dp[n]=max{0,dp[n-1]}+a_n
其中,dp[n]表示以a_n结尾的最大子序列和。
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 1724个

财富等级: 堆金积玉

 楼主| 发表于 2020-9-17 00:16:09 | 显示全部楼层
本帖最后由 aimisiyou 于 2020-9-17 00:17 编辑

_$ (defun f1(lst)
  (setq sum 0 llst nil flag t i 0 n (length lst) )
  (while (< i n)
     (setq ea (nth i lst))
     (if (> ea 0)
             (progn
                    (setq sum (+ sum ea))
            (setq flag t)
                        (if (= i (- n 1)) (setq llst (cons sum llst)))
                  )
                 (progn
                         (if (and flag (> sum 0))
                             (progn
                                 (setq llst (cons ea (cons sum llst)))
                                 (setq sum 0 flag nil)
                                  )
                  (if (null flag) (setq llst (cons ea llst)))
                      )
                   )
          )
          (setq i (+ i 1))
        )
   (reverse llst)
)
(setq lst '(-3 -8 10 10 -6 -7 -8 10 15 -8 -9 10 16 -8))
(setq lst (reverse (f1 (reverse (f1 lst)))))
F1
(-3 -8 10 10 -6 -7 -8 10 15 -8 -9 10 16 -8)
(20 -6 -7 -8 25 -8 -9 26)
_$ (reverse (f1 (reverse (f1 '( 10 10 )))))
(20)
_$ (reverse (f1 (reverse (f1 '( -10 -10 )))))
nil
_$

点评

aeo
(f1 '(-3 -8 10 10 -6 -7 -8 10 15 -8 -9 10 16 -8)) (20 -6 -7 -8 25 -8 -9 26 -8) ???????  详情 回复 发表于 2020-9-18 16:27
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 407个

财富等级: 日进斗金

发表于 2020-9-17 08:37:35 | 显示全部楼层
算法与数据结构,大学蒙过去了
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 474个

财富等级: 日进斗金

发表于 2020-9-18 15:27:29 | 显示全部楼层
本帖最后由 aeo 于 2020-9-18 15:28 编辑

;https://www.cnblogs.com/hapjin/p/5404705.html
;①任何负的 子序列都不可能是最大子序列和 的前缀

;②当加上 下标 j 所在的元素 使得 当前序列的和变成负数时,根据①,可以从 j+1 处重新开始计算下一段子序列的和。

public static int maxSubSum2(int[] arr) {
        int maxSum = 0;
        int thisSum = 0;
        for (int i = 0; i < arr.length; i++) {
            thisSum += arr;
            if (thisSum > maxSum)// thisSum在[0,maxSum]之间时不需要任何处理
                maxSum = thisSum;
            else if (thisSum < 0)// 说明加上当前元素使得子序列为负数了,那么抛弃这段子序列(相当于thisSum赋值为0),从下一轮for开始
                thisSum = 0;
        }
        return maxSum;
    }
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 474个

财富等级: 日进斗金

发表于 2020-9-18 16:27:23 | 显示全部楼层
aimisiyou 发表于 2020-9-17 00:16
_$ (defun f1(lst)
  (setq sum 0 llst nil flag t i 0 n (length lst) )
  (while (< i n)

(f1 '(-3 -8 10 10 -6 -7 -8 10 15 -8 -9 10 16 -8))
(20 -6 -7 -8 25 -8 -9 26 -8)
???????

点评

的确还存在问题。负数或总和为负数对后续无增益效果。  详情 回复 发表于 2020-9-18 17:04
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 1724个

财富等级: 堆金积玉

 楼主| 发表于 2020-9-18 17:04:49 | 显示全部楼层
本帖最后由 aimisiyou 于 2020-9-18 17:06 编辑
aeo 发表于 2020-9-18 16:27
(f1 '(-3 -8 10 10 -6 -7 -8 10 15 -8 -9 10 16 -8))
(20 -6 -7 -8 25 -8 -9 26 -8)
???????

这是数据预处理,得到初始数据。(删去首尾负数,中间连续正数项合并)
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|申请友链|小黑屋|手机版|Archiver|辽公网安备|晓东CAD家园 ( 辽ICP备15016793号 )  

GMT+8, 2020-10-1 12:00 , Processed in 0.184753 second(s), 76 queries , Gzip On, WinCache On.

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表