学步园

public class Test {
    // 最大连续子序列积
    // 假设有集合A,Max[n]表示从A[0]~A[n]的以A[n]结尾的最大连续子序列积，
    // Min[n]表示从A[0]~A[n]的以A[n]结尾的最小子序列积，则有如下递推式
    // Max[n] = Max{ Max[n-1]*A[n], A[n], Min[n-1]*A[n] }
    // Min[n] = Min{ Max[n-1]*A[n], A[n], Min[n-1]*A[n] }

    private static void getMaxProduct(float[] a) {
        float[] maxArr = new float[a.length];
        float[] minArr = new float[a.length];
        maxArr[0] = a[0];
        minArr[0] = a[0];
        float maxProduct = a[0];
        int maxStartInx = 0;    //最大连续序列积开始坐标
        int maxEndInx = 0;  //最大连续序列积结束坐标
        int curMaxStartInx = 0; //当前最大积开始坐标
        int preMaxStartInx = 0; //上一个最大积开始坐标
        int curMinStartInx = 0; //当前最小积开始坐标
        int preMinStartInx = 0; //上一个最小积开始坐标

        for (int i = 1; i < a.length; i++) {
            maxArr[i] = Math.max(a[i], Math.max(maxArr[i - 1] * a[i], minArr[i - 1] * a[i]));
            minArr[i] = Math.min(a[i], Math.min(maxArr[i - 1] * a[i], minArr[i - 1] * a[i]));

            if (maxProduct < maxArr[i]) {
                maxProduct = maxArr[i];
                
                //序列坐标更新
                if (maxArr[i] == a[i]) {
                    maxStartInx = maxEndInx = i;
                } else if (maxArr[i] == maxArr[i - 1] * a[i]){
　　　　　　　　　　　　maxStartInx = preMaxStartInx;
　　　　　　　　　　　　maxEndInx = i;
                } else {
                    // 如果maxArr[i]是通过minArr[i-1]*a[i]得到，
                    // 说明其序列开始坐标等于上一个元素的最小连续序列积的开始坐标
                    maxStartInx = preMinStartInx;
                    maxEndInx = i;
                }
            }

            //记录当前最小连续子序列积的开始坐标
            if (minArr[i] == a[i]) {
                curMinStartInx = i;
            } else if (minArr[i] == maxArr[i - 1] * a[i]) {
                curMinStartInx = preMaxStartInx;
            }

            //记录当前最大连续子序列积的开始坐标
            if (maxArr[i] == a[i]) {
                curMaxStartInx = i;
            } else if (maxArr[i] == minArr[i - 1] * a[i]){
                curMaxStartInx = preMinStartInx;
            }

            preMaxStartInx = curMaxStartInx;
            preMinStartInx = curMinStartInx;
        }

        System.out.println("MaxProduct: " + maxProduct + " Start: " + maxStartInx + " End: " + maxEndInx);
    }

    public static void main(String[] args) {
        float[] a = {1.4f, 8, 0.9f, -2, 0.7f, -4, 0, 3, 9, -1, 0.55f, 100, -2};
        getMaxProduct(a);
    }
}