最大連續子序列和

tonyh

試使用動態規劃法(DP)，求最大連續子序列和。
               
index              0   1    2   3   4   5   6   7   8
data[ ]           -2   1  -3   4  -1   2   1  -5   4
curMaxSum    -2   1  -2   4   3   5   6   1   5
totMaxSum     -2   1   1   4   4   5   6   6   6

範例輸入 1：-2 1 -3 4 -1 2 1 -5 4
範例輸出 1：6

範例輸入 2：0 -2 3 5 -1 2
範例輸出 2：9

1. import java.io.BufferedReader;
   
2. import java.io.InputStreamReader;
   
3. 
   
4. public class Ch01 {
   
5. 
   
6.         BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
   
7.         String raw[];
   
8.         int curMaxSum, totMaxSum;
   
9.         Ch01() throws Exception
   
10.         {
    
11.                 raw=br.readLine().split(" ");
    
12.                 for(int i=0, len=raw.length; i<len; i++)
    
13.                 {
    
14.                         int t=Integer.parseInt(raw[i]);
    
15.                         if(i==0)
    
16.                         {
    
17.                                 curMaxSum=t;
    
18.                                 totMaxSum=t;
    
19.                         }
    
20.                         curMaxSum=Math.max(curMaxSum+t, t);
    
21.                         totMaxSum=Math.max(curMaxSum, totMaxSum);
    
22.                 }
    
23.                 System.out.println(totMaxSum);
    
24.         }
    
25.         public static void main(String[] args) throws Exception{
    
26.                 new Ch01();
    
27.         }
    
28. }

複製代碼

1. import java.io.BufferedReader;
   
2. import java.io.InputStreamReader;
   
3. 
   
4. public class Ch01 {
   
5. 
   
6.         BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
   
7.         String raw[];
   
8.         int len, data[];
   
9.         Ch01() throws Exception
   
10.         {
    
11.                 raw=br.readLine().split(" ");
    
12.                 len=raw.length;
    
13.                 data=new int[len];
    
14.                 for(int i=0; i<len; i++)
    
15.                         data[i]=Integer.parseInt(raw[i]);
    
16.                 System.out.println(maxSubArray(data));
    
17.         }
    
18. 
    
19.         int maxSubArray(int data[])
    
20.         {
    
21.                 int curMaxSum=data[0];
    
22.                 int totMaxSum=data[0];
    
23.                 for(int i=1; i<len; i++)
    
24.                 {
    
25.                         curMaxSum=Math.max(curMaxSum+data[i],data[i]);
    
26.                         totMaxSum=Math.max(totMaxSum, curMaxSum);
    
27.                 }
    
28.                 return totMaxSum;
    
29.         }
    
30. 
    
31.         public static void main(String[] args) throws Exception{
    
32.                 new Ch01();
    
33.         }
    
34. }
    
35. /*
    
36. -2 11 -4 13 -5 -2
    
37. 11-4+13=20
    
38. 
    
39. -2 1 -3 4 -1 2 1 -5 4
    
40. 4-1+2+1=6
    
41. 
    
42. 1 -2 3 5 -3 2
    
43. 3+5=8
    
44. 
    
45. 0 -2 3 5 -1 2
    
46. 3+5-1+2=9
    
47. 
    
48. -9 -2 -3 -5 -3
    
49. -2=-2
    
50. */

複製代碼