Board logo

標題: 最大連續子序列和 [打印本頁]
作者: tonyh    時間: 2023-2-3 19:51     標題: 最大連續子序列和

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

  4. public class Ch01 {

  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;

  4. public class Ch01 {

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

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

  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

  39. -2 1 -3 4 -1 2 1 -5 4
  40. 4-1+2+1=6

  42. 1 -2 3 5 -3 2
  43. 3+5=8

  45. 0 -2 3 5 -1 2
  46. 3+5-1+2=9

  48. -9 -2 -3 -5 -3
  49. -2=-2
  50. */
複製代碼
作者: 劉愷鈞    時間: 2023-2-10 19:59

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

  5. public class f314 {
  6.         BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  7.         String raw[];
  8.         int curmaxsum,totmaxsum;
  9.         f314() throws IOException
  10.         {
  11.                 raw=br.readLine().split(" ");
  12.                 for(int i=0;i<raw.length;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 IOException {
  26.                 new f314();
  27.         }
  28. }
複製代碼
作者: 董宸佑    時間: 2023-2-10 20:03

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

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

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

  28. }
複製代碼
作者: 陳宥穎    時間: 2023-2-10 20:04

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


  6. public class Ch01 {
  7.         BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  8.         int crr,tot,data;
  9.         String raw[];
  10.         Ch01() throws Exception
  11.         {
  12.                 raw=br.readLine().split(" ");
  13.                 for(int i=0; i<raw.length; i++)
  14.                 {
  15.                         data=Integer.parseInt(raw[i]);
  16.                         if(i==0)
  17.                         {
  18.                                 crr=data;
  19.                                 tot=data;
  20.                         }
  21.                         crr=Math.max(crr+data, data);
  22.                         tot=Math.max(crr, tot);
  23.                 }
  24.                 System.out.println(tot);
  25.         }
  26.         public static void main(String[] args) throws Exception {
  27.                 new Ch01();
  28.         }
  29.         //-2 1 -3 4 -1 2 1 -5 4
  30. }
複製代碼
作者: 孫嘉駿    時間: 2023-2-10 20:04

  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 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. }
複製代碼
作者: 李穎俊    時間: 2023-2-10 20:05

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

  4. public class P1 {

  6.         BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  7.         String raw[];
  8.         int cMS, tMS;
  9.         P1() throws Exception
  10.         {
  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(cMS+t, t);
  18.                        tMS=Math.max(tMS, cMS);
  19.                }
  20.                System.out.println(tMS);
  21.         }
  22.         public static void main(String[] args) throws Exception{
  23.                 new P1();
  24.         }
  25. }
複製代碼
作者: 洪承廷    時間: 2023-2-10 20:05

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


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

  32. }
複製代碼
作者: 林祐霆    時間: 2023-2-10 21:02

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

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

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

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

  27. }
複製代碼
作者: 蘇韋誠    時間: 2023-2-12 12:28

  1. package hahaha;

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

  6. public class ha {

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




歡迎光臨 種子論壇 | 高雄市資訊培育協會學員討論區 (http://istak.org.tw/seed/) Powered by Discuz! 7.2