#17 | |
108703029(CTHua) |
本題使用演算法:DP 解題思路: 假設矩陣大小為N 1.矩陣降維 利用dp建立row sum 1、1+2...1+~N的row array,(1+~N)-(1+2)便可得(3+~N)的row array 利用此點可以壓縮矩陣成為一維的陣列,接著計算MSS(Maximum Subsequence)。 2.計算MSS 依然是用DP,利用Kadane's演算法,假設今天有一個數列 1 2 3 -7 1,前三項sum=6,加入第四項時sum=-1, 這時可得知計入第四項會拉低後面的總和,先記錄max_sum=sum(=6),接著總和又從0開始計算。(這個算法的時間複雜度是O(N))
|