[發問] offset與定義名稱

帖子: 186
主題: 6
精華: 0
積分: 218
點名: 0
作業系統: win7
軟體版本: office 2007
閱讀權限: 20
性別: 男
註冊時間: 2012-11-12
最後登錄: 2014-4-15

8^#

發表於 2013-4-10 23:37 | 只看該作者

回復 5# Hsieh

這個只處理到A1:{A2,A3...An}中最大的子序列
沒有處理A2:{A3,A4...An},A3:{A4,A5,...An}...的最大子序列

帖子: 186
主題: 6
精華: 0
積分: 218
點名: 0
作業系統: win7
軟體版本: office 2007
閱讀權限: 20
性別: 男
註冊時間: 2012-11-12
最後登錄: 2014-4-15

7^#

發表於 2013-4-10 23:34 | 只看該作者

回復 6# ML089

=MAX(SUBTOTAL(9,OFFSET(A$1,ROW()-1,,-ROW(INDIRECT("1:"&ROW())))))
基本上是http://emn178.pixnet.net/blog/post/88907691中的「改良式暴力法」
也就是第一列回傳A1中最大的
第二列回傳{A1:A2,A2}最大的
第三列回傳{A1:A3,A2:A3,A3}最大的
第n列回傳{A1:An,A2:An,...An-1:An}中最大的
然後再取這n列最大的，即是「最大子序列」

這雖然不是Kadane's演算法，但是結果會一樣
(而且因為excel沒有辦法直接設變數，所以我用很詭異的方式模擬的Kadane's演算法，因此時間複雜度也不會比較好)

我的(原文中第二個)問題是：如何不使用這個補助列，直接得出最大子序列？
把你的公式中的row()改成row(offset($A$A,,,counta(A:A),))，也不對…
=MAX(MAX(SUBTOTAL(9,OFFSET(A$1,ROW(offset($A$A,,,counta(A:A),))-1,,-ROW(INDIRECT("1:"&ROW(offset($A$A,,,counta(A:A),))))))))

版主 Rank: 7 Rank: 7 Rank: 7

ML089

帖子: 2025
主題: 13
精華: 0
積分: 2053
點名: 0
作業系統: WIN7
軟體版本: Office2007
閱讀權限: 100
性別: 男
來自: 台北市
註冊時間: 2011-3-2
最後登錄: 2024-3-14

論壇榮譽勳章論壇贊助勳章熱烈參與勳章 2014馬年全勤獎章 2015羊年全勤獎章 2016猴年全勤獎章

6^#

發表於 2013-4-10 19:40 | 只看該作者

啊，這樣會有什麼差別嗎？
Bodhidharma 發表於 2013-4-10 19:05

那公式是模擬你原先的 B1公式

下式是模擬超版的 B1公式
=MAX(SUBTOTAL(9,OFFSET(A$1,ROW()-1,,-ROW(INDIRECT("1:"&ROW())))))
三鍵輸入

{...} 表示需要用 CTRL+SHIFT+ENTER 三鍵輸入公式

Hsieh

超級版主 Rank: 8 Rank: 8

帖子: 4901
主題: 44
精華: 24
積分: 4916
點名: 292
作業系統: Windows 7
軟體版本: Office 20xx
閱讀權限: 150
性別: 男
來自: 台北
註冊時間: 2010-4-30
最後登錄: 2025-11-29

2024年全勤獎章 2023年全勤獎章 2022虎年全勤獎章 2021牛年全勤獎章 2020鼠年全勤獎章 2019 豬年全勤獎章 2018 狗年全勤獎章 2017 雞年全勤獎章 2016猴年全勤獎章 2015羊年全勤獎章 2014馬年全勤獎章 2013蛇年全勤獎章 2012龍年全勤獎章論壇貢獻勳章熱心公益勳章 2011兔年全勤獎章

5^#

發表於 2013-4-10 19:23 | 只看該作者

回復 2# Bodhidharma

試試看動態範圍與遞增範圍加總陣列

maximum subarray.rar (7.79 KB)

學海無涯_不恥下問

帖子: 186
主題: 6
精華: 0
積分: 218
點名: 0
作業系統: win7
軟體版本: office 2007
閱讀權限: 20
性別: 男
註冊時間: 2012-11-12
最後登錄: 2014-4-15

4^#

發表於 2013-4-10 19:05 | 只看該作者

回復 Bodhidharma

B1可用下式替代
=SUBTOTAL(9,OFFSET(A$1,,,ROW()))
ML089 發表於 2013-4-10 10:24

啊，這樣會有什麼差別嗎？

版主 Rank: 7 Rank: 7 Rank: 7

ML089

帖子: 2025
主題: 13
精華: 0
積分: 2053
點名: 0
作業系統: WIN7
軟體版本: Office2007
閱讀權限: 100
性別: 男
來自: 台北市
註冊時間: 2011-3-2
最後登錄: 2024-3-14

論壇榮譽勳章論壇贊助勳章熱烈參與勳章 2014馬年全勤獎章 2015羊年全勤獎章 2016猴年全勤獎章

3^#

發表於 2013-4-10 10:24 | 只看該作者

回復 2# Bodhidharma

B1可用下式替代
=SUBTOTAL(9,OFFSET(A$1,,,ROW()))

{...} 表示需要用 CTRL+SHIFT+ENTER 三鍵輸入公式

帖子: 186
主題: 6
精華: 0
積分: 218
點名: 0
作業系統: win7
軟體版本: office 2007
閱讀權限: 20
性別: 男
註冊時間: 2012-11-12
最後登錄: 2014-4-15

2^#

發表於 2013-4-10 03:24 | 只看該作者

本帖最後由 Bodhidharma 於 2013-4-10 03:27 編輯

回復 1# Bodhidharma

B1換一種寫法：
=SUM(OFFSET($A$1,IFERROR(INDEX(MATCH(2,1/(OFFSET($B$1,,,ROW()-1,)<0)),),0),,ROW()-IFERROR(INDEX(MATCH(2,1/(OFFSET($B$1,,,ROW()-1,)<0)),),0),))
用index(match(2,1/tolast<0),)取代{LARGE(IF(tolast<0,ROW(tolast),""),1)}的陣列公式 (note:奇怪我當初幹麻不用max要用large...)
這樣子的話，不過用tolast或(OFFSET($B$1,,,ROW()-1,)都可以了
所以看起來是陣列公式的問題？不過還是搞不懂是什麼原理…

不過即使這樣改，我還是不知道如何將這種DP的東西寫成一個式子(D1)