java 求解子數組子字元串的問題合集

問題一：連續子數組的最大和

輸入一個整型數組，數組裡有正數也有負數。數組中一個或連續的多個整數組成一個子數組。求解所有子數組的和的最大值。要求時間是o（n）。

思路：

動态規劃的思想。

用函數f(i)表示第i個數字結尾的子數組的最大和，我們求出最大的f(i)即可。

p[i] i=0或f(i-1)<=0

f(i)=f(i-1)+p[i] i>0且f(i-1)>0

我們用result記錄最大值，sum表示f(i)。

代碼

import java.util.*;
public class SymmetricSubsequence {

    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        ArrayList<Integer> arr=new ArrayList<Integer>();
        int n=sc.nextInt();
        for(int i=;i<n;i++){
            arr.add(sc.nextInt());
        }

        int sum=,result=arr.get();
        for(int i=;i<arr.size();i++){
            if(sum<){
                sum=;//如果sum成負值了，再接着加的結果不如自己本身大，是以舍棄之前的和，重新開始。
            }
            //比較result和sum大小，result記住大的；
            sum+=arr.get(i);
            if(result<sum) result=sum;
        }
        System.out.println(result); 
    }

}

           

問題二 找最長對稱的連續子字元串

輸入一個字元串，輸出該字元串中對稱的子字元串的最大長度。比如 輸入字元串“google”，由于該字元串裡最長的對稱子字元串是“goog”