返回列表 發帖

Rank: 8Rank: 8
1# 跳轉到 » 倒序看帖
打印
tT
tonyh發表於 2023-5-27 20:08 | 只看該作者

最大連續子序列和

本帖最後由 tonyh 於 2023-6-10 19:50 編輯

試使用動態規劃法(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;

  4. public class Ch01 {

  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.     }

  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. }
複製代碼
收藏 分享

Rank: 1
2#
王法棣發表於 2023-6-3 20:59 | 只看該作者
本帖最後由 王法棣 於 2023-6-4 00:50 編輯
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;

  5. public class Ch1 {
  6.         BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  7.         int q;
  8.         int a[];
  9.         int max=0;
  10.         String raw[];
  11.         Ch1() throws Exception
  12.         {
  13.                 raw=br.readLine().split(" ");
  14.                 a=new int[raw.length+1];
  15.                 for(int i=1;i<=raw.length;i++)
  16.                 {
  17.                         a[i]=a[i-1]+Integer.parseInt(raw[i-1]);
  18.                        
  19.                         if(Integer.parseInt(raw[i-1])>a[i])
  20.                                 a[i]=Integer.parseInt(raw[i-1]);
  21.                 }
  22.                 for(int i=1;i<=raw.length;i++)
  23.                 {
  24.                         if(max<a[i])
  25.                                 max=a[i];
  26.                 }
  27.                 System.out.println(max);
  28.                
  29.                
  30.         }

  32.         public static void main(String[] args) throws Exception {
  33.                 new Ch1();
  34.         }

  36. }
複製代碼

TOP

Rank: 1
3#
陳依彤發表於 2023-6-3 21:05 | 只看該作者
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,sum=0,Max=0;
  4. stringstream ss;
  5. string str;
  6. int main()
  7. {
  8.     cin.tie(0);
  9.     cin.sync_with_stdio(0);
  10.     getline(cin,str);
  11.     ss<<str;
  12.     while(ss>>n){
  13.         if(sum+n>n)sum=sum+n;
  14.         else sum=n;
  15.         if(Max<sum)Max=sum;
  16.     }
  17.     cout<<Max;

  19.     return 0;
  20. }
複製代碼

TOP

Rank: 1
4#
許志捷發表於 2023-6-3 22:38 | 只看該作者
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int sum,Max,n;
  4. string s;
  5. stringstream ss;
  6. int main()
  7. {
  8.     cin.tie(0);
  9.     cin.sync_with_stdio(0);
  10.     ss.clear();
  11.     getline(cin,s);
  12.     ss<<s;
  13.     while(ss>>n)
  14.     {
  15.         if((n+sum)>n)
  16.             sum+=n;
  17.         else
  18.             sum=n;
  19.         if(Max<sum)
  20.             Max=sum;
  21.     }
  22.     cout<<Max<<"\n";
  23.     return 0;
  24. }
複製代碼

TOP

Rank: 1
5#
王秉鈞發表於 2023-6-10 19:42 | 只看該作者
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. stringstream ss;
  4. string str;
  5. int n,index=0;
  6. int cMaxSum, fMaxSum;
  7. int main()
  8. {
  9.     cin.tie(0);
  10.     cin.sync_with_stdio(0);
  11.     getline(cin,str);
  12.     ss<<str;
  13.     while(ss>>n)
  14.     {
  15.         if(index==0)
  16.         {
  17.             cMaxSum=n;
  18.             fMaxSum=n;
  19.         }
  20.         else
  21.         {
  22.             cMaxSum=max(n+cMaxSum,n);
  23.             fMaxSum=max(fMaxSum,cMaxSum);
  24.         }
  25.         index++;
  26.     }
  27.     cout<<fMaxSum<<endl;
  28.     return 0;
  29. }
複製代碼

TOP

Rank: 1
6#
張博竣發表於 2023-6-10 19:44 | 只看該作者
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;

  5. public class Ch1 {
  6.         BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  7.         int q;
  8.         int a[];
  9.         int max=0;
  10.         String raw[];
  11.         Ch1() throws Exception
  12.         {
  13.                 raw=br.readLine().split(" ");
  14.                 a=new int[raw.length+1];
  15.                 for(int i=1;i<=raw.length;i++)
  16.                 {
  17.                         a[i]=a[i-1]+Integer.parseInt(raw[i-1]);
  18.                        
  19.                         if(Integer.parseInt(raw[i-1])>a[i])
  20.                                 a[i]=Integer.parseInt(raw[i-1]);
  21.                 }
  22.                 for(int i=1;i<=raw.length;i++)
  23.                 {
  24.                         if(max<a[i])
  25.                                 max=a[i];
  26.                 }
  27.                 System.out.println(max);
  28.                
  29.                
  30.         }

  32.         public static void main(String[] args) throws Exception {
  33.                 new Ch1();
  34.         }

  36. }
複製代碼

TOP

Rank: 1
7#
曾元瑜發表於 2023-6-10 19:45 | 只看該作者
  1. import java.io.BufferedReader;
  2. import java.io.InputStreamReader;


  5. public class Ch01 {
  6.         int maxS,maxV;
  7.         String raw[];
  8.         BufferedReader br=new BufferedReader(new InputStreamReader(System.in));       
  9.         Ch01()throws Exception
  10.         {
  11.                 raw=br.readLine().split(" ");
  12.                 for(int i=0;i<raw.length;i++)
  13.                 {
  14.                         if(i==0)
  15.                         {
  16.                                 maxS=Integer.parseInt(raw[i]);
  17.                                 maxV=Integer.parseInt(raw[i]);
  18.                         }
  19.                         else
  20.                         {
  21.                                 int t=Integer.parseInt(raw[i]);
  22.                                 maxS=Math.max(maxS+t, t);
  23.                                 maxV=Math.max(maxV, maxS);
  24.                         }
  25.                 }
  26.                 System.out.println(maxV);
  27.         }
  28.         public static void main(String[] args) throws Exception{
  29.                 new Ch01();
  30.         }
  31. }
複製代碼

TOP

Rank: 1
8#
許洧熏發表於 2023-6-10 19:52 | 只看該作者
  1. import java.io.BufferedReader;
  2. import java.io.InputStreamReader;

  4. public class Ch01 {

  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.     }

  28.     public static void main(String[] args) throws Exception{
  29.         new Ch01();
  30.     }
  31. }
複製代碼

TOP

Rank: 1
9#
黃子倢發表於 2023-6-10 20:00 | 只看該作者
  1. import java.io.BufferedReader;
  2. import java.io.InputStreamReader;

  4. public class E346 {

  6.     BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  7.     String raw[];
  8.     int maxS, maxV;
  9.     E346() 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.     }

  28.     public static void main(String[] args) throws Exception{
  29.         new E346();
  30.     }
  31. }
複製代碼

TOP

Rank: 1
10#
林土水發表於 2023-6-10 20:28 | 只看該作者
  1. import java.io.BufferedReader;
  2. import java.io.InputStreamReader;


  5. public class Ch01 {
  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.                         System.out.println(maxV);
  25.                 }

  27.         }


  30.         public static void main(String[] args)throws Exception{
  31.                 new Ch01();

  33.         }

  35. }
複製代碼

TOP

返回列表