最大連續子序列和

tonyh

試使用動態規劃法(DP)，求最大連續子序列和。

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

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

範例輸入 3：-2 11 -4 13 -5 -2
範例輸出 3：20

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

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

Java

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 maxS, maxV;
   
9.     Ch01() throws Exception
   
10.     {
    
11.         raw=br.readLine().split(" ");
    
12.         for(int i=0, len=raw.length; i<len; i++)
    
13.         {
    
14.             if(i==0)
    
15.             {
    
16.                 maxS=Integer.parseInt(raw[i]);
    
17.                 maxV=Integer.parseInt(raw[i]);
    
18.             }else
    
19.             {
    
20.                 int t=Integer.parseInt(raw[i]);
    
21.                 maxS=Math.max(maxS+t, t);
    
22.                 maxV=Math.max(maxV, maxS);
    
23.             }
    
24.         }
    
25.         System.out.println(maxV);
    
26.     }
    
27. 
    
28.     public static void main(String[] args) throws Exception{
    
29.         new Ch01();
    
30.     }
    
31. }

複製代碼

C++

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. stringstream ss;
   
4. string str;
   
5. int maxS, maxV;
   
6. int main()
   
7. {
   
8.     cin.tie(0);
   
9.     cin.sync_with_stdio(0);
   
10.     getline(cin, str);
    
11.     ss<<str;
    
12.     int t;
    
13.     ss>>t;
    
14.     maxS=t;
    
15.     maxV=t;
    
16.     while(ss>>t)
    
17.     {
    
18.         maxS=max(maxS+t, t);
    
19.         maxV=max(maxV, maxS);
    
20.     }
    
21.     cout<<maxV<<endl;
    
22.     return 0;
    
23. }

複製代碼