Java怎么求一個整型數(shù)組中最大連續(xù)子序列的和

這篇文章主要介紹“Java怎么求一個整型數(shù)組中最大連續(xù)子序列的和”，在日常操作中，相信很多人在Java怎么求一個整型數(shù)組中最大連續(xù)子序列的和問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”Java怎么求一個整型數(shù)組中最大連續(xù)子序列的和”的疑惑有所幫助！接下來，請跟著小編一起來學(xué)習(xí)吧！

/**

• 動態(tài)規(guī)劃(Dynamic Programming)：

•  1)將待求解的問題分解為若干個子問題(即:將求解的過程分為若干階段)，按順序求解子問題，前一子問題的解，為后一子問題的求解提供了有用的信息；

  
  

•  2)在求解任一子問題時(shí)，列出可能的局部解，通過決策保留那些有可能達(dá)到最優(yōu)的局部解，丟棄其它的局部解；

  
  

•  3)依次解決各子問題，最后一個子問題的解就是初始問題的解。

• 問題：求一個整型數(shù)組中最大連續(xù)子序列的和，數(shù)組中既包含正整數(shù)也包含負(fù)整數(shù)。

• 舉例：數(shù)組int[] array = {1, -3, 7, 8, -4, 10, -19, 11};中最大連續(xù)子序列為：7, 8, -4, 10 它們的和為21

*/

public class DP {

/**
 * 暴力求解
 *
 * 時(shí)間復(fù)雜度：O(N^2)
 */
public static int maxSubSumByEnum(int[] array) {
    int maxSum = 0;
    int begin = 0;
    int end = 0;

    /**
     * 1)第i次循環(huán)結(jié)束后可以找到：以第i個元素為起點(diǎn)的連續(xù)子序列的最大值。
     * 2)i表示序列的起點(diǎn)，j表示序列的終點(diǎn)。
     * 3)每一次循環(huán)中將終點(diǎn)不斷向后移動：每次向后移動一位并且計(jì)算當(dāng)前序列的和，循環(huán)結(jié)束后，我們就可以得到本次循環(huán)中子序列和最大的值。
     */
    for (int i = 0; i < array.length; i++) { //

        int tempSum = 0;

        for (int j = i; j < array.length; j++) {
            tempSum += array[j];

            if (tempSum > maxSum) {
                maxSum = tempSum;
                begin = i;
                end = j;
            }
        }
    }
    System.out.println("begin:" + begin + " end:" + end);
    return maxSum;
}

/**
 * 動態(tài)規(guī)劃
 *
 * 時(shí)間復(fù)雜度：O(N)
 *
 * 要點(diǎn)：
 *      1)若當(dāng)前階段中連續(xù)子序列的和小于0，則進(jìn)入下一階段，同時(shí)確定下一階段的起點(diǎn)并將下一階段的和初始化為0。
 *      2)只有當(dāng)前階段的總和大于歷史最大總和時(shí)，才會去更新數(shù)組中最大連續(xù)子序列的起點(diǎn)和終點(diǎn)。
 */
public static int maxSubSumByDP(int[] array) {

    int maxSum = 0;     // 數(shù)組中，最大連續(xù)子序列的和
    int begin = 0;      // 數(shù)組中，最大連續(xù)子序列的起點(diǎn)
    int end = 0;        // 數(shù)組中，最大連續(xù)子序列的終點(diǎn)
    int tempSum = 0;    // 當(dāng)前階段中，連續(xù)子序列的和
    int tempBegin = 0;  // 當(dāng)前階段中，連續(xù)子序列的起點(diǎn)

    for (int i = 0; i < array.length; i++) {

        tempSum += array[i];

        if (tempSum < 0) {             // 若當(dāng)前階段中連續(xù)子序列的和小于0，則進(jìn)入下一階段

            tempSum = 0;        // 下一階段的和進(jìn)行歸零處理
            tempBegin = i + 1;  // 下一階段的起點(diǎn)

        } else if (tempSum > maxSum) { // 若當(dāng)前階段的總和大于歷史最大總和，則更新數(shù)組中最大連續(xù)子序列的起點(diǎn)和終點(diǎn)。
            maxSum = tempSum;
            begin = tempBegin;
            end = i;
        }
    }
    System.out.println("begin:" + begin + " end:" + end);
    return maxSum;
}

public static void main(String[] args) {
    int[] array = {1, -3, 7, 8, -4, 10, -19, 11};
    int dpMax = maxSubSumByDP(array);
    System.out.println(dpMax);
    int enumMax = maxSubSumByEnum(array);
    System.out.println(enumMax);
}

}

到此，關(guān)于“Java怎么求一個整型數(shù)組中最大連續(xù)子序列的和”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識，請繼續(xù)關(guān)注億速云網(wǎng)站，小編會繼續(xù)努力為大家?guī)砀鄬?shí)用的文章！