【160326 18:00】最大子序列之和 1

此篇講的是截止時間至 3 月 26 日 18:00 的最大子序列之和 1 之小結。相應的題目，可以見王建民老師的部落格中第一題：

http://www.cnblogs.com/wangjm1975/p/5411663.html

問題簡析

這是一個最優化問題，并且要求時間複雜度為 \(O(n)\)。這樣一來，首先想到的應該是動态規劃思想。

動态規劃是求解最優化問題的一種思想。

動态規劃的核心，是要尋找一種看待問題的方式：這種角度以某種方式将原問題劃分為有限的若幹階段；每個階段可以有若幹狀态，但隻有一個最優狀态；目前階段的最優狀态，可以用某種确定的方式，從過去某些階段的某些狀态直接得到；這種方式，隻與這些階段的狀态有關，而與這些狀态是如何得到的無關。這樣一來，如果我們能夠在某個階段找到确定的最優狀态，就能夠逐層遞推，找到原問題的最優解。

在這裡：

• 有限的階段，即是子問題；
• 目前階段的最優狀态，即是局部最優解；
• 目前階段的最優狀态，可以用某種确定的方式，從過去某些階段的某些狀态直接得到，即是最優子結構性質；
• 這種方式，隻與這些階段的狀态有關，而與這些狀态是如何得到的無關，即是無後效性質。

也就是說，動态規劃的核心，是要尋找一種具有最優子結構的無後效的問題拆解方式。

以下是用 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 分，采取扣分制與體驗分相結合的方式。具體來說：

• 每見到一處問題/缺陷，扣除該類問題/缺陷相應的分數；
• 與此同時，還會有 \(\pm 1\) 分的體驗分浮動：博文結構清晰、排版整潔、代碼清爽等情況酌情加分，反之扣分。

10 分

• 作業遲交超過 24 小時
• 未能完成任務

5 分

• 沒有送出代碼（至少核心代碼）

2 分

• 作業遲交，但未超過 24 小時
• 博文代碼沒有使用「代碼模式」編輯（這很重要，已經是第五次作業了，是以提升權重，望引起重視）
• 博文中，非代碼内容使用了「代碼模式」編輯（這很重要，已經是第五次作業了，是以提升權重，望引起重視）
• 程式沒有正确計算最大子數組的和
• 算法的時間複雜度超過 \(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		32.5
20132907		8	38
20132917	32	7.5	39.5
20132922	28		35.5
20132927	20.5	6	26.5
20132935	24.5		33.5
20132967	20
20132970	22.5
20132984	29		36
20132985	27.5	5.5
20133005		5	29.5
20133009	25		30.5
20133012
20133014	14		19
20133018		3	22
20133039		2.5
20133040		1.5
20133045	21
20133048
20133051
20133054	31
20133057			23.5
20133059	19.5		27
20133062	12	4.5	16.5
20133064
20133070
20133075
20133078
20133081
20133087
20133100
20132899		3.5	10
20132901			14.5
20132903			31.5
20132910	28.5		37.5
20132912
20132919			40
20132924			41
20132958
20132959
20132965			34.5
20132971
20132980			35
20133004			34
20133008
20133010	8.5
20133013
20133017
20133019
20133024		9.5
20133027
20133031	18
20133042
20133043
20133044
20133047	15	1	16
20133056
20133058	25.5
20133063
20133066	21.5
20133073
20133077
20133079
20133088	10.5
20133093		4
20133099	17
20133101

其他問題

如果有同學認為自己的作業，評分與預期有差；或者有新的補充。

那麼建議你通過部落格園站内短消息的方式聯系我，或者在你的作業後回帖留言（記得 @ 我）。

你也可以在這篇博文下直接回複。不過不推薦你這樣做……

軟體工程的意義

歡迎參看下面的文章：

http://www.cnblogs.com/ChenMeng0518/p/5460435.html