返回列表 發帖

最大連續子序列和

本帖最後由 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;

  3. public class Ch01 {

  4.     BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  5.     String raw[];
  6.     int maxS, maxV;
  7.     Ch01() throws Exception
  8.     {
  9.         raw=br.readLine().split(" ");
  10.         for(int i=0, len=raw.length; i<len; i++)
  11.         {
  12.             if(i==0)
  13.             {
  14.                 maxS=Integer.parseInt(raw[i]);
  15.                 maxV=Integer.parseInt(raw[i]);
  16.             }else
  17.             {
  18.                 int t=Integer.parseInt(raw[i]);
  19.                 maxS=Math.max(maxS+t, t);
  20.                 maxV=Math.max(maxV, maxS);
  21.             }
  22.         }
  23.         System.out.println(maxV);
  24.     }

  25.     public static void main(String[] args) throws Exception{
  26.         new Ch01();
  27.     }
  28. }
複製代碼
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. }
複製代碼

本帖最後由 王法棣 於 2023-6-4 00:50 編輯
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;

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

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

  33. }
複製代碼

TOP

  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;

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

TOP

  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

  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

  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;

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

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

  33. }
複製代碼

TOP

  1. import java.io.BufferedReader;
  2. import java.io.InputStreamReader;


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

TOP

  1. import java.io.BufferedReader;
  2. import java.io.InputStreamReader;

  3. public class Ch01 {

  4.     BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  5.     String raw[];
  6.     int maxS, maxV;
  7.     Ch01() throws Exception
  8.     {
  9.         raw=br.readLine().split(" ");
  10.         for(int i=0, len=raw.length; i<len; i++)
  11.         {
  12.             if(i==0)
  13.             {
  14.                 maxS=Integer.parseInt(raw[i]);
  15.                 maxV=Integer.parseInt(raw[i]);
  16.             }else
  17.             {
  18.                 int t=Integer.parseInt(raw[i]);
  19.                 maxS=Math.max(maxS+t, t);
  20.                 maxV=Math.max(maxV, maxS);
  21.             }
  22.         }
  23.         System.out.println(maxV);
  24.     }

  25.     public static void main(String[] args) throws Exception{
  26.         new Ch01();
  27.     }
  28. }
複製代碼

TOP

  1. import java.io.BufferedReader;
  2. import java.io.InputStreamReader;

  3. public class E346 {

  4.     BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  5.     String raw[];
  6.     int maxS, maxV;
  7.     E346() throws Exception
  8.     {
  9.         raw=br.readLine().split(" ");
  10.         for(int i=0, len=raw.length; i<len; i++)
  11.         {
  12.             if(i==0)
  13.             {
  14.                 maxS=Integer.parseInt(raw[i]);
  15.                 maxV=Integer.parseInt(raw[i]);
  16.             }else
  17.             {
  18.                 int t=Integer.parseInt(raw[i]);
  19.                 maxS=Math.max(maxS+t, t);
  20.                 maxV=Math.max(maxV, maxS);
  21.             }
  22.         }
  23.         System.out.println(maxV);
  24.     }

  25.     public static void main(String[] args) throws Exception{
  26.         new E346();
  27.     }
  28. }
複製代碼

TOP

  1. import java.io.BufferedReader;
  2. import java.io.InputStreamReader;


  3. public class Ch01 {
  4.         BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  5.     String raw[];
  6.     int maxS, maxV;
  7.     Ch01() throws Exception
  8.         {
  9.                 raw=br.readLine().split(" ");
  10.                 for(int i=0, len=raw.length; i<len; i++)
  11.                 {
  12.                         if(i==0)
  13.                         {
  14.                                 maxS=Integer.parseInt(raw[i]);
  15.                                 maxV=Integer.parseInt(raw[i]);
  16.                         }else
  17.                         {
  18.                                 int t=Integer.parseInt(raw[i]);
  19.                                 maxS=Math.max(maxS+t,t);
  20.                                 maxV=Math.max(maxV,maxS);
  21.                         }
  22.                         System.out.println(maxV);
  23.                 }

  24.         }


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

  27.         }

  28. }
複製代碼

TOP

返回列表