發表新討論
#17
[C++]解題報告

108703029(CTHua)
a027. Maximum Sum -- UVA | From: [140.119.192.4] | 發表日期 : 2020-05-03 01:48

本題使用演算法: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))

   

 
文章性質 :
|
| 回應文章 | 回原始文章
ZeroJudge Forum