本帖最後由 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- import java.io.BufferedReader;
- import java.io.InputStreamReader;
- public class Ch01 {
- BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
- String raw[];
- int curMaxSum, totMaxSum;
- Ch01() throws Exception
- {
- raw=br.readLine().split(" ");
- for(int i=0, len=raw.length; i<len; i++)
- {
- int t=Integer.parseInt(raw[i]);
- if(i==0)
- {
- curMaxSum=t;
- totMaxSum=t;
- }
- curMaxSum=Math.max(curMaxSum+t, t);
- totMaxSum=Math.max(curMaxSum, totMaxSum);
- }
- System.out.println(totMaxSum);
- }
- public static void main(String[] args) throws Exception{
- new Ch01();
- }
- }
複製代碼- import java.io.BufferedReader;
- import java.io.InputStreamReader;
- public class Ch01 {
- BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
- String raw[];
- int len, data[];
- Ch01() throws Exception
- {
- raw=br.readLine().split(" ");
- len=raw.length;
- data=new int[len];
- for(int i=0; i<len; i++)
- data[i]=Integer.parseInt(raw[i]);
- System.out.println(maxSubArray(data));
- }
- int maxSubArray(int data[])
- {
- int curMaxSum=data[0];
- int totMaxSum=data[0];
- for(int i=1; i<len; i++)
- {
- curMaxSum=Math.max(curMaxSum+data[i],data[i]);
- totMaxSum=Math.max(totMaxSum, curMaxSum);
- }
- return totMaxSum;
- }
- public static void main(String[] args) throws Exception{
- new Ch01();
- }
- }
- /*
- -2 11 -4 13 -5 -2
- 11-4+13=20
- -2 1 -3 4 -1 2 1 -5 4
- 4-1+2+1=6
- 1 -2 3 5 -3 2
- 3+5=8
- 0 -2 3 5 -1 2
- 3+5-1+2=9
- -9 -2 -3 -5 -3
- -2=-2
- */
複製代碼 |