趣味SQL题：188. 买卖股票的最 佳时机 IV

〇〇

如果只有很长的英文，加几个utf8字符就会审核

sql_tigerliu

〇〇 发表于 2024-9-7 18:19
如果只有很长的英文，加几个utf8字符就会审核

那进入审核的帖子也应该及时处理一下, 时间长了就变成垃圾了

sql_tigerliu

--match_recognize写法做了简化
with d as (
select '1,3,3,5,7,10,7,6,8,9,7,5,4,6,8,9,11,2,5,7' s from dual
)
,stock_trade as
(
select level as seq,to_number(regexp_substr(s,'[^,]+',1,level)) as val from d connect by level<=regexp_count(s,',')+1
),mid1 as
(select *
from stock_trade
match_recognize(
order by seq
measures
match_number() as mn
,first(val) as min_val
,last(val) as max_val
one row per match
pattern ( st up+)
   define
        st as val<next(val)
       ,up as val>=prev(val)
   )
)select sum(max_val-min_val) as max_earn
from (select * from mid1 order by max_val-min_val desc)
where rownum<=3;

newkid

sql_tigerliu 发表于 2024-9-7 20:57
那进入审核的帖子也应该及时处理一下, 时间长了就变成垃圾了

我刚刚放出来一个，也不知道为什么进去的。
现在itpub对海外IP做了限制，普通人只能看帖，我只有在家里的IP地址才能发帖，还是开了绿色通道才可以的。

newkid

sql_tigerliu 发表于 2024-9-7 21:32
--match_recognize写法做了简化with d as (select '1,3,3,5,7,10,7,6,8,9,7,5,4,6,8,9,11,2,5,7' s from du ...

你这个还不完善，当K=1即只买卖一次时，你得到的答案是9，其实应该是10

sql_tigerliu

newkid 发表于 2024-9-8 01:51
你这个还不完善，当K=1即只买卖一次时，你得到的答案是9，其实应该是10

把问题看简单了, 看来不用递归很难实现. 放弃了

newkid

我的做法：
第一步：先找出所有尽可能长的连续上升线段，这一步用match_recognize很容易做到。

第一条：1,3,3,5,7,10
第二条：6,8,9
第三条：4,6,8,9,11
第四条：2,5,7

所有的子线段都不是最 佳时机，比如第一条线中的子线段 (3,5)或(3,7)就应该抛弃，最 佳买入点只存在于这些线段的低点，卖出点则在高点中选择。

第二步：
每条线段的低点和其他后续线段的高点也可能组成最 佳时机，比如第一条线和第三条线组成(1,11)。但是这仅限于比前面高点更高的高点，比如第一条和第二条的组合(1,9)就应该抛弃，还不如前面的(1,10); 第一条和第四条的组合(1,7)也应该抛弃，因为前面已经出现了(1,11)这种更佳的。
同理，第二条和第三条也有**组合(6,11)，而第二条和第四条组成的(6,7)则应抛弃。

这一步的结果是(1,10)(1,11)(6,9)(6,11)(4,11)(2,7)
看起来很像笛卡尔积，我想办法用match_recognize找了出来。

所以match_recognize进行了预处理优化，第一个找出尽可能长的连续上升段，第二个则找出高点呈上升趋势

第三步就是老生常谈，在第二步结果中找出1-k对组合让其利润最大化，用递归WITH实现，要注意下次交易必须在上次结束之后。

with d1 as (
-- 第一次匹配：求出所有尽可能长的连续上升段, 每个段输出一行
select *
  from stock
  match_recognize (
  order by dt
  measures min(dt) as dt1
          ,max(dt) as dt2
          ,min(price) as price1
          ,max(price) as price2
  one row per match
  pattern(start_point a+)
  define a as price>=prev(price)  
  )
)
,d2 as (
-- 第二次匹配：用每个上升段的起点，去配对后面的其他上升段的高点，这些构成了可能的最 佳买入卖出时机。
-- 利用after match skip to next row避免了笛卡尔积，每个段都向后匹配，最终只输出高点呈上升趋势的那些段，下降的没有意义
select *
  from d1
  match_recognize (
  order by dt1
  measures --match_number() as grp_id
          --,classifier() as flag
           start_point.dt1 as start_dt
          ,start_point.price1 as start_price
  all rows per match
  after match skip to next row
  pattern(start_point ( {- a -}| b)*)   ---- 把a从输出中去除
  define a as price2<max(price2) --- 这些不是上升的，可以从输出中去除
        ,b as price2=max(price2) --- 这些是需要留下的高点上升趋势
  )
)
,t(end_dt,path,amount,cnt) as ( ---- 递归尝试从d2结果中取 1-K 个，看看哪个组合盈利最多
select dt2,'('||start_dt||':'||start_price||'->'||dt2||':'||price2||')',price2-start_price,1
from d2
union all
select d2.dt2,t.path||'('||d2.start_dt||':'||d2.start_price||'->'||d2.dt2||':'||d2.price2||')'
      ,t.amount+d2.price2-d2.start_price
      ,t.cnt+1
  from t,d2
where t.end_dt<d2.start_dt
       and t.cnt<:k
)
select * from t
order by amount desc
fetch first 1 rows with ties;

sql_tigerliu

newkid 发表于 2024-9-8 10:45
我的做法：第一步：先找出所有尽可能长的连续上升线段，这一步用match_recognize很容易做到。第一条：1,3,3 ...

解题思路很重要, 我那个只实现了第一步. 还需要match_recognize的一些**用法, 最终还需要递归来帮忙. 只不过这个递归比纯暴力的递归减少了很多工作量.  这类问题, 如果没有思路, 用**语言也不好实现.
学习了!