回答編集履歴

テキスト修正

2019/05/30 11:21

投稿

jun68ykt

スコア9058

test CHANGED Viewed

@@ -402,7 +402,7 @@
-- [https://repl.it/@jun68ykt/Q284975](https://repl.it/@jun68ykt/Q284975)
+- [https://repl.it/@jun68ykt/Q192033](https://repl.it/@jun68ykt/Q192033)

テキスト修正

2019/05/30 11:21

投稿

jun68ykt

スコア9058

test CHANGED Viewed

@@ -337,3 +337,81 @@
 上記は二重のループがないので、 `O(n)` で済んでいます。
+### 追記2
+上記のコードが正解ではないことを、コメントからご指摘、ありがとうございます。
+自分でやろうと思ったのですが、たぶんどこかに良質な回答のコードがあるだろうと思って調べましたところ、以下を見つけました。
+- Stackoverflow: [Maximum sum sublist? の回答](https://stackoverflow.com/a/15063394)
+> If you want the start and end slice indices, too, you need to track a few more bits of information (note this is still O(1) space and O(n) time, it's just a bit hairier):
+```python
+def mssl(l):
+    best = cur = 0
+    curi = starti = besti = 0
+    for ind, i in enumerate(l):
+        if cur+i > 0:
+            cur += i
+        else: # reset start position
+            cur, curi = 0, ind+1
+        if cur > best:
+            starti, besti, best = curi, ind+1, cur
+    return starti, besti, best
+```
+上記に対して、
+`A = [-1, 5, -10, 9, -4, 18, -10, 30, 23, -26, 37, 48, -19, -13, 31]`
+を与えたサンプルを以下に作成しました。
+- [https://repl.it/@jun68ykt/Q284975](https://repl.it/@jun68ykt/Q284975)
+上記を実行すると
+> (3, 12, 125)
+と表示されます。このコードの場合、 `(開始, 終端, 合計)`　を返しており、`終端` は含まない形式で返してくれます。

テキスト修正

2019/05/30 04:59

投稿

jun68ykt

スコア9058

test CHANGED Viewed

@@ -258,7 +258,7 @@
-55 個のすべての部分リストを調べなくても、以下で大丈夫かなと思います。
+すべての部分リストを調べなくても、以下で大丈夫かなと思います。
@@ -336,4 +336,4 @@
-上記は `O(n)` になっているかと思います。
+上記は二重のループがないので、 `O(n)` で済んでいます。

テキスト修正

2019/05/29 14:24

投稿

jun68ykt

スコア9058

test CHANGED Viewed

@@ -249,3 +249,91 @@
 以上、参考になれば幸いです。
+### 追記
+55 個のすべての部分リストを調べなくても、以下で大丈夫かなと思います。
+```python3
+def solution(A):
+    start = None
+    end = None
+    if len(A) == 0:
+        return 0, start, end
+    # 開始インデクスを求める
+    start = 0
+    tmp = 0
+    for i in range(len(A)):
+        tmp += A[i]
+        if tmp <= 0 and i+1 < len(A):
+            start = i+1
+    # 終端インデクスを求める
+    tmp = 0
+    max_total = None
+    for j in range(start, len(A)):
+        tmp += A[j]
+        if max_total is None or tmp > max_total:
+            end = j
+            max_total = tmp
+    return max_total, start, end
+if __name__ == '__main__':
+    A = [-1, 5, -10, 9, -4, 18, -10, 30, 23, -26, 37, 48, -19, -13, 31]
+    ans = solution(A)
+    print(ans)
+```
+> (120, 5, 11)
+上記は `O(n)` になっているかと思います。

テキスト修正

2019/05/29 13:33

投稿

jun68ykt

スコア9058

test CHANGED Viewed

@@ -40,7 +40,7 @@
-ご質問に上げられているコードでは何が拙いかというと、合計の比較の際に、以下のようにしている箇所です。
+まず、ご質問に上げられているコードでは何が拙いかというと、合計の比較の際に、以下のようにしている箇所です。
@@ -82,17 +82,13 @@
-あるはずです。
-まずこれを抑えたうえで、二重のループによって、合計を算出すべき部分リストが 55 種類出現しているかという観点で、見直されるとよいかと思います。
+あるはずです。これを抑えたうえで、二重のループによって、合計を算出すべき部分リストが 55 種類出現しているかという観点で、見直されるとよいかと思います。
-具体的な修正ですが、ご質問にあるコードをなるべく活かすとすると、たとえば以下のようになるかと思います。
+次に、具体的な修正案ですが、ご質問にあるコードをなるべく活かすとすると、たとえば以下のようになるかと思います。
@@ -172,9 +168,7 @@
-もうひとつ別解を以下に上げます。
+もうひとつ別解を以下に挙げます。
 ```python3
@@ -224,7 +218,23 @@
-上記で、 `sorted` の第1引数になる、内包表記によるリストは、以下のようなタプル
+上記で、 `sorted` の第1引数になる、内包表記によるリスト
+```pyhon3
+[(sum(A[i:j+1]), i, j)
+    for i in range(len(A))
+    for j in range(len(A))
+    if i <= j
+]
+```
+は、以下のようなタプル

テキスト修正

2019/05/29 12:25

投稿

jun68ykt

スコア9058

test CHANGED Viewed

@@ -30,11 +30,11 @@
-`(合計値の最大値, 合計が最大になる部分配列の開始インデクス, 合計が最大になる部分配列の終端インデクス)`
+`(合計値の最大値, 合計が最大になる部分リストの開始インデクス, 合計が最大になる部分配列の終端インデクス)`
-という要素が3つのタプルで、`合計が最大になる部分配列の終端インデクス` も、合計の対象に**含まれる**　と解釈しました。以下、これを前提とした回答になります。
+という要素が3つのタプルで、`合計が最大になる部分リストの終端インデクス` も、合計の対象に**含まれる**　と解釈しました。以下、これを前提とした回答になります。
@@ -74,7 +74,7 @@
-開始インデクスを `i` ( 0<=i<len(A) )とすると 終端インデクスの取り得る場合の数は `len(A)-i` 個　で 、いま `len(A) は` 10 なので、比較対象となる合計値は、**重複を考慮しなければ（すなわち、異なる部分配列の要素の合計が一致してもそれらは個別に数えるとして、）**
+開始インデクスを `i` ( 0<=i<len(A) )とすると 終端インデクスの取り得る場合の数は `len(A)-i` 個　で 、いま `len(A) は` 10 なので、比較対象となる合計値は、**重複を考慮しなければ（すなわち、異なる部分リストの要素の合計が(たまたま)一致してもそれらは個別に数えるとして、）**
@@ -154,7 +154,7 @@
-と表示されます。開始インデクス `0` 、終端インデクス `6`(※これも含む） であるAの部分配列
+と表示されます。開始インデクス `0` 、終端インデクス `6`(※これも含む） であるAの部分リスト
 ```
@@ -228,11 +228,11 @@
-`(部分配列の要素の合計値, 部分配列の開始インデクス, 部分配列の終端インデクス)`
+`(部分リストの要素の合計値, 部分リストの開始インデクス, 部分リストの終端インデクス)`
-を、`A` の部分配列のすべてについて含み、このリストの長さは先に求めた、場合の数の **55**  になります。
+を、`A` の部分リストのすべてについて含み、このリストの長さは先に求めた、場合の数の **55**  になります。