返回列表 發帖

最大連續子序列和

本帖最後由 tonyh 於 2023-2-10 19:51 編輯

試使用動態規劃法(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. public class Ch01 {

  4.         BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  5.         String raw[];
  6.         int curMaxSum, totMaxSum;
  7.         Ch01() throws Exception
  8.         {
  9.                 raw=br.readLine().split(" ");
  10.                 for(int i=0, len=raw.length; i<len; i++)
  11.                 {
  12.                         int t=Integer.parseInt(raw[i]);
  13.                         if(i==0)
  14.                         {
  15.                                 curMaxSum=t;
  16.                                 totMaxSum=t;
  17.                         }
  18.                         curMaxSum=Math.max(curMaxSum+t, t);
  19.                         totMaxSum=Math.max(curMaxSum, totMaxSum);
  20.                 }
  21.                 System.out.println(totMaxSum);
  22.         }
  23.         public static void main(String[] args) throws Exception{
  24.                 new Ch01();
  25.         }
  26. }
複製代碼
  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 len, data[];
  7.         Ch01() throws Exception
  8.         {
  9.                 raw=br.readLine().split(" ");
  10.                 len=raw.length;
  11.                 data=new int[len];
  12.                 for(int i=0; i<len; i++)
  13.                         data[i]=Integer.parseInt(raw[i]);
  14.                 System.out.println(maxSubArray(data));
  15.         }

  16.         int maxSubArray(int data[])
  17.         {
  18.                 int curMaxSum=data[0];
  19.                 int totMaxSum=data[0];
  20.                 for(int i=1; i<len; i++)
  21.                 {
  22.                         curMaxSum=Math.max(curMaxSum+data[i],data[i]);
  23.                         totMaxSum=Math.max(totMaxSum, curMaxSum);
  24.                 }
  25.                 return totMaxSum;
  26.         }

  27.         public static void main(String[] args) throws Exception{
  28.                 new Ch01();
  29.         }
  30. }
  31. /*
  32. -2 11 -4 13 -5 -2
  33. 11-4+13=20

  34. -2 1 -3 4 -1 2 1 -5 4
  35. 4-1+2+1=6

  36. 1 -2 3 5 -3 2
  37. 3+5=8

  38. 0 -2 3 5 -1 2
  39. 3+5-1+2=9

  40. -9 -2 -3 -5 -3
  41. -2=-2
  42. */
複製代碼

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

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

TOP

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

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

  22.         public static void main(String[] args) throws Exception {
  23.                 new Ch01();
  24.         }

  25. }
複製代碼

TOP

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


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

TOP

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

  3. public class P1 {

  4.         BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  5.         String raw[];
  6.         int cMS, tMS;
  7.         P1() throws Exception
  8.         {
  9.                for (int i = 0,len=raw.length; i < len; i++) {
  10.                        int t=Integer.parseInt(raw[i]);
  11.                        if (i==0) {
  12.                                cMS=t;
  13.                                tMS=t;
  14.                        }
  15.                        cMS=Math.max(cMS+t, t);
  16.                        tMS=Math.max(tMS, cMS);
  17.                }
  18.                System.out.println(tMS);
  19.         }
  20.         public static void main(String[] args) throws Exception{
  21.                 new P1();
  22.         }
  23. }
複製代碼

TOP

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


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

  29. }
複製代碼

TOP

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

  4. public class Squeeezy {
  5.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  6.         String raw[];
  7.         int c, t;

  8.         Squeeezy() throws Exception {
  9.                 raw = br.readLine().split(" ");
  10.                 for (int i = 0, len = raw.length; i < len; i++) { // i=0;i<raw.length;i++
  11.                         t = Integer.parseInt(raw[i]);
  12.                         if (i == 0)
  13.                                 c = 0;
  14.                         t = 0;
  15.                         c = Math.max(c + t, t);
  16.                         t = Math.max(c, t);
  17.                 }
  18.                 System.out.println(t);
  19.         }

  20.         public static void main(String[] args) throws Exception {
  21.                 new Squeeezy();
  22.         }

  23. }
複製代碼
林祐霆

TOP

  1. package hahaha;

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

  4. public class ha {

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

TOP

返回列表