Max Sum(動態規劃)

原創

http://acm.hdu.edu.cn/showproblem.php?pid=1003

　　題目要求求出一個序列裡面的最大序列和，序列要求是連續的，給出最大序列和，序列首元素下標和尾元素下標，按特定的格式輸出。

　　解題思路：

　　　　動態規劃，我們可以將所有序列按以序列中的元素a[i](i=1~n)結尾進行分類，比如：

　　　　以a[1]結尾的序列有：a[1]

　　　　以a[2]結尾的序列有：a[1]a[2],a[2]

　　　　以a[3]結尾的序列有：a[1]a[2]a[3],a[2][3],a[3]

　　　　...... 

　　　　這樣所有序列都會包含在其中，一共被分為n大組，每大組裡麵包含許多小序列，從每大組裡面選出最大的序列和，這樣會選出n個

　　　　序列和，再從n個序列和中選出最大的就是題目要求的最大序列和了。

　　　　動態規劃公式演算：

　　　　之前說過有n大組，用dp[]存儲從每大組中選出來的最大序列和，其中

　　　　dp[1]=a[1]

　　　　dp[2]=max(a[1]a[2],a[2]),即從兩個序列裡面選出序列和最大的，既然只需要比較序列和，兩個數比較大小，兩個數同時減去一

　　　　個相同的數不影響比較，那麼兩個序列都先把元素a[2]減去，這樣就成了dp[2]=max(dp[1]+a[2],a[2])。

　　　　dp[3]=max(a[1]a[2]a[3],a[2][3],a[3]),寫成max(a[1]a[2]+a[3],a[2]+[3],0+a[3])更容易理解動態規劃思想,3個序列都先把

　　　　a[3]提出變成max(a[1]a[2],a[2],0),再變成max(max(a[1]a[2],a[2]),0)，三個數比較，可以先比較其中2個，再和第三個比較，

　　　　可以發現max(a[1]a[2],a[2])就是dp[2]，所以max(a[1]a[2],a[2],0)就是max(dp[2],0),加回a[3]，max(dp[2]+a[3],a[3])。

　　　　所以我們可以輕而易舉的按順序求出n大組的序列和，然後再從n個序列和中求出最大的。

　　　　關於求最大序列和的首尾元素索引：

　　　　我們在求某個dp[i]的時候，代表目前是從以a[i]結尾的序列和中求出序列和最大的存入dp[i]中，所以尾元素可以得知。

　　　　尾元素得到，可以往回找到首元素。

Java AC

 1 import java.util.*;
 2 
 3 public class Main {
 4 
 5     public static void main(String[] args) {
 6         Scanner reader=new Scanner(System.in);
 7         int T=reader.nextInt();
 8         int count=1;
 9         while(T>0) {
10             int N=reader.nextInt();
11             int a[]=new int[N+1];
12             for(int i=1;i<=N;i++) {
13                 a[i]=reader.nextInt();
14             }
15             int dp=a[1];
16             int sum_Max=dp;
17             int start=1;
18             int end=1;
19             for(int i=2;i<=N;i++) {
20                 dp=dp+a[i]>a[i]?(dp+a[i]):a[i];    //動態存儲以a[1]~a[n]結尾的序列組的最大序列和
21                 if(dp>sum_Max) {
22                     sum_Max=dp;
23                     end=i;    //結尾索引
24                 }
25             }
26             //尋找開頭索引
27             int sum=0;
28             for(int i=end;i>=1;i--) {
29                 sum+=a[i];
30                 if(sum==sum_Max) {
31                     start=i;
32                     //這裡不能break,當序列中存在多個序列具有同樣的最大序列和,題目要求輸出第一個被找到的序列
33                 }
34             }
35             System.out.println("Case "+count+":");
36             System.out.println(sum_Max+" "+start+" "+end);
37             if(T!=1) {
38                 System.out.println();
39             }
40             T--;
41             count++;
42         }
43     }
44 
45 }

21:21:39

2018-08-19