題目連結:
跟
這題幾乎一樣,只差在這次是要求子區域總和最小之值為何。
4
0 -2 -7 0 9 2
-6 2 -4
1 -4 1 -1 8 0
-2 10 9 116 24 -121 30 14 2 119 122 28 -53 125 -71 87 -57 42 -111 125
-33 91 -121 30 -28 1 -16 97 -11 68 -24 103 -126 98 -61 33 48 109
-88 67 -72 77 -107 95 -78 23 -86 45 -4 28 -121 73 -57 20 -122 9
68 -97 79 -68 122 -42 88 -22 0 -116 55 -44 68 -109 43 -32 103 -54
122 -41 62 -114 113 -32 29 -22 99 -11 38 -60 88 -83 28 -83 122 -56
100 -86 63 -49 111 -77 91 -88 69 -110
因為跟題目大意提及的那題只差在該題求最大,而本題求最小。
所以將本題中的陣列數字加上負號反轉後,再套用求最大子區域的方式做。最後將結果加上負號反轉回來就是所求。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。