求最大子序列和

aimisiyou · 发表于 2020-9-15 10:38:30

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

您需要登录才可以下载或查看，没有账号？立即注册

×

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

给定一数组，如35，-7，-20,30，-15，-18,35，求该数组最大子序列和。

aimisiyou · 发表于 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;
}

aimisiyou · 发表于 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));
}

aimisiyou · 发表于 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
_$

aimisiyou · 发表于 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
_$

aimisiyou · 发表于 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结尾的最大子序列和。

aimisiyou · 发表于 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
_$

kyky1002 · 发表于 2020-9-17 08:37:35

算法与数据结构，大学蒙过去了

aeo · 发表于 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;
}

aeo · 发表于 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)
???????

aimisiyou · 发表于 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)
???????

这是数据预处理，得到初始数据。（删去首尾负数，中间连续正数项合并）

账号		自动登录	找回密码
密码			立即注册

[研讨] 求最大子序列和

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

点评

点评

点评