共計 2014 個字符，預計需要花費 6 分鐘才能閱讀完成。

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

/**

動態規劃 (Dynamic Programming)：

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

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

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

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

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

*/

public class DP {
 *  暴力求解
 *
 *  時間復雜度：O(N^2)
 */
public static int maxSubSumByEnum(int[] array) {
 int maxSum = 0;
 int begin = 0;
 int end = 0;
 /**
 * 1) 第 i 次循環結束后可以找到：以第 i 個元素為起點的連續子序列的最大值。 * 2)i 表示序列的起點，j 表示序列的終點。 * 3) 每一次循環中將終點不斷向后移動：每次向后移動一位并且計算當前序列的和，循環結束后，我們就可以得到本次循環中子序列和最大的值。 */
 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;
 *  動態規劃
 *
 *  時間復雜度：O(N)
 *
 *  要點： * 1) 若當前階段中連續子序列的和小于 0，則進入下一階段，同時確定下一階段的起點并將下一階段的和初始化為 0。 * 2) 只有當前階段的總和大于歷史最大總和時，才會去更新數組中最大連續子序列的起點和終點。 */
public static int maxSubSumByDP(int[] array) {
 int maxSum = 0; //  數組中，最大連續子序列的和
 int begin = 0; //  數組中，最大連續子序列的起點
 int end = 0; //  數組中，最大連續子序列的終點
 int tempSum = 0; //  當前階段中，連續子序列的和
 int tempBegin = 0; //  當前階段中，連續子序列的起點
 for (int i = 0; i   array.length; i++) { tempSum += array[i];
 if (tempSum   0) { //  若當前階段中連續子序列的和小于 0，則進入下一階段
 tempSum = 0; //  下一階段的和進行歸零處理
 tempBegin = i + 1; //  下一階段的起點
 } else if (tempSum   maxSum) { //  若當前階段的總和大于歷史最大總和，則更新數組中最大連續子序列的起點和終點。 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);
}

}

到此，關于“Java 怎么求一個整型數組中最大連續子序列的和”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注丸趣 TV 網站，丸趣 TV 小編會繼續努力為大家帶來更多實用的文章！