【160326 18:00】最大サブシーケンスの和1

締め切りは3月26日18:00までの最大子序列の和1の小結である.相応のテーマは、王建民先生のブログの第一題を見ることができます.
http://www.cnblogs.com/wangjm1975/p/5411663.html
問題の概要
これは最適化問題であり,要求時間複雑度は(O(n))である.こうなると、まず思いつくのはダイナミックプランニング思想です.
動的計画は最適化問題を解く思想である.
ダイナミックプランニングの核心は、問題を見る方法を探すことです.この角度はある方法で元の問題を限られたいくつかの段階に分けます.各段階にはいくつかの状態があるが、最適な状態は1つしかない.現在の段階の最適状態は、過去のいくつかの段階のいくつかの状態から直接得ることができる.この方式は,これらの段階の状態にのみ関係し,これらの状態がどのように得られるかには関係ない.これにより,ある段階で決定された最適状態を見つけることができれば,層毎に繰返し,元の問題の最適解を見つけることができる.
ここでは、

の限られた段階、すなわちサブ問題である.

現在の段階の最適状態、すなわち局所最適解である.

現在の段階の最適状態は、過去のいくつかの段階のいくつかの状態から直接得ることができる、すなわち最適サブ構造特性である.

この方式は、これらの段階の状態にのみ関係し、これらの状態がどのように得られるかに関係なく、すなわち、後効性のない性質である.

すなわち,動的計画の核心は,最適サブ構造を有する後効のない問題分解方式を探すことである.
以下はPythonで簡単に書いた本題の参考です.

def maxSubArraySum (nums):
    if not nums:
        return None
    elif 1 == len (nums):
        return nums[0]

    local_max, global_max = nums[0], nums[0]

    for i in xrange (1, len (nums)):
        local_max  = max (local_max + nums[i], nums[i])
        global_max = max (local_max, global_max)

    return global_max

if __name__ == '__main__':
    test_cases = [[], [0], [1], [1, 2, 3], [-3, -1, -2],
                  [9, 8, 5, 2, -5, 6, 2, -2]]
    for nums in test_cases:
        print "The maxSubArraySum of", nums, "is", maxSubArraySum (nums)

採点基準
今回の宿題は10点満点で、減点制と体験点を組み合わせた方式を採用した.具体的には、

問題/欠陥が1つ見られるたびに、この種の問題/欠陥の対応する点数を差し引く.

と同時に、(pm 1)点の体験点が浮動します:博文の構造がはっきりしていて、レイアウトがきれいで、コードがさわやかであるなどの状況は適宜加点して、逆に減点します.

10点

作業遅延24時間以上

タスクを完了できませんでした

5点

コミットコード(少なくともコアコード)

なし
2点

作業遅納、24時間

を超えない

博文コードは「コードモード」編集を使用していない(これは重要で、すでに5回目の作業なので、重みを上げて重視したい)

博文では、非コードコンテンツは「コードモード」編集(これは重要で、すでに5回目の作業なので、重みを上げて重視したい)

を使用しています.

プログラムは、最も大きなサブ配列の和

を正しく計算していない.

アルゴリズムの時間的複雑度は(O(n))

を超える.
1.5点

設計思想を述べていない

は分析をまとめていない.あるいは総括の中で実際の内容がありません:今回のプログラミングに対する分析あるいは出会った問題と解決方法

1点

実行結果断図

なし

出力エラーの結果

平凡(trivial)の場合は処理されていません:入力配列が空であればどうしますか?

項目ごとに1～3点

追加の質問(ブログ後の回答説明を参照)

採点結果
学号
前回までの作業得点小計
160326 18:00
小計
20122951
23
7
30
20132897
24
9
33
20132900
11
6.5
17.5
20132902
26
6.5
32.5
20132907
30
8
38
20132917
32
7.5
39.5
20132922
28
7.5
35.5
20132927
20.5
6
26.5
20132935
24.5
9
33.5
20132967
20
8
28
20132970
22.5
0
22.5
20132984
29
7
36
20132985
27.5
5.5
33
20133005
24.5
5
29.5
20133009
25
5.5
30.5
20133012
27.5
5
32.5
20133014
14
5
19
20133018
19
3
22
20133039
29.5
2.5
32
20133040
26.5
1.5
28
20133045
21
8
29
20133048
28
1.5
29.5
20133051
24.5
8
32.5
20133054
31
2.5
33.5
20133057
17.5
6
23.5
20133059
19.5
7.5
27
20133062
12
4.5
16.5
20133064
24.5
6
30.5
20133070
25
6
31
20133075
26
6
32
20133078
29
7
36
20133081
24.5
6.5
31
20133087
24.5
5.5
30
20133100
28
8
36
20132899
6.5
3.5
10
20132901
9
5.5
14.5
20132903
22.5
9
31.5
20132910
28.5
9
37.5
20132912
32
7.5
39.5
20132919
31
9
40
20132924
32
9
41
20132958
30
8
38
20132959
30
7.5
37.5
20132965
28
6.5
34.5
20132971
26
6.5
32.5
20132980
28
7
35
20133004
28.5
5.5
34
20133008
22.5
5
27.5
20133010
8.5
2.5
11
20133013
19
8
27
20133017
21
6.5
27.5
20133019
29
6
35
20133024
24
9.5
33.5
20133027
24
9.5
33.5
20133031
18
5.5
23.5
20133042
17.5
5
22.5
20133043
5
0
5
20133044
4.5
0
4.5
20133047
15
1
16
20133056
24
3.5
27.5
20133058
25.5
8
33.5
20133063
21
5.5
26.5
20133066
21.5
0
21.5
20133073
14.5
8.5
23
20133077
24
5.5
29.5
20133079
24
5.5
29.5
20133088
10.5
0
10.5
20133093
21.5
4
25.5
20133099
17
4
21
20133101
25
8
33
その他の質問
もし同級生が自分の宿題だと思っているなら、採点は予想と悪い.あるいは新しい補充があります.では、ブログ園構内のショートメッセージで連絡したり、宿題の後にメッセージを書いたりすることをお勧めします(私を覚えています).あなたもこのブログの下で直接返事することができます.でもお勧めしませんが...
ソフトウェアエンジニアリングの意義
次の記事を参照してください.http://www.cnblogs.com/ChenMeng0518/p/5460435.html