關于Java求最大子段和

public static int maxSubArray(int[] nums) {
int maxSum = nums[0];
int curSum = nums[0];
for (int i = 1; i< nums.length; i++) {
curSum = Math.max(nums[i], curSum + nums[i]);
maxSum = Math.max(maxSum, curSum);
}
return maxSum;
}
public static void main(String[] args) {
int[] nums = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
int maxSum = maxSubArray(nums);
System.out.println(maxSum); //輸出6
}

以上是用Java實現(xiàn)求最大子段和的代碼段。算法思路是從數(shù)組的第一個數(shù)開始循環(huán)，不斷更新當前子段和和最大子段和。如果當前子段和小于0，則將當前子段和更新為當前循環(huán)到的數(shù)，否則將當前子段和加上當前循環(huán)到的數(shù)更新為新的當前子段和。在每次更新當前子段和之后，將最終最大子段和更新為當前最大子段和和之前計算出來的最大子段和的較大值。最后返回最大子段和即可。

以數(shù)組{-2,1,-3,4,-1,2,1,-5,4}為例，循環(huán)過程如下：

i=0：maxSum=-2, curSum=-2
i=1：maxSum=1, curSum=1
i=2：maxSum=1, curSum=-2
i=3：maxSum=4, curSum=4
i=4：maxSum=4, curSum=3
i=5：maxSum=4, curSum=5
i=6：maxSum=6, curSum=6
i=7：maxSum=6, curSum=1
i=8：maxSum=6, curSum=5

第8次循環(huán)結束后，最大子段和為6，輸出結果即可。