louisfghbvc的部落格

題目連結:  https://onlinejudge.org/external/7/787.pdf

題目大意:  找出最大連續子序列乘積

思路:  N = 100，可以暴力O(N^3)，不過要注意這題數字很大，要用大整數。可以用C++刻。不過Java這時候方便就在這。

優化，O(N^2)，枚舉所有的i, j。用滑動窗口的概念去想，每個窗口計算乘積並記錄最大值。

再優化，O(N). Dp。維持local最大，local最小值。當數值為負，交換local最大、local最小，因為相乘會相反。維持local的兩個值，

，0的情況，則要判斷是不是現在的數字能夠較大或較小。並記錄更新最大值。算是蠻神奇的思維。 

代碼:  

import java.util.*;
import java.math.BigInteger;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int []arr = new int[105];
        int n;
        while(input.hasNext()){
            n = 0;
            while(input.hasNextInt()){
                arr[n] = input.nextInt();
                if(arr[n] == -999999) break;
                n++;
            }
            
            BigInteger res = BigInteger.valueOf(arr[0]);
            BigInteger imax = BigInteger.valueOf(arr[0]);
            BigInteger imin = BigInteger.valueOf(arr[0]);
            for(int i = 1; i < n; ++i){
                BigInteger num = BigInteger.valueOf(arr[i]);
                if(num.compareTo(BigInteger.ZERO) == -1){
                    BigInteger tmp = imax;
                    imax = imin;
                    imin = tmp;
                }
                imax = num.max(imax.multiply(num)); // max(num, imax*num)
                imin = num.min(imin.multiply(num));
                res = res.max(imax);
            }
            System.out.println(res);
        }
    }
    
}