最大子段和問題,指在一個數(shù)列中找到連續(xù)的子序列,使該子序列的和最大,即得到一個最大子段和。在Java中,我們可以通過動態(tài)規(guī)劃的思路來求解最大子段和。
public static int maxSubArray(int[] nums) {
int maxSum = nums[0];
int curSum = 0;
for (int num : nums) {
if (curSum< 0) {
curSum = num;
} else {
curSum += num;
}
maxSum = Math.max(maxSum, curSum);
}
return maxSum;
}
上面的代碼中,我們定義了兩個變量maxSum和curSum。其中,maxSum表示最大子段和,curSum表示當前子段和。我們通過遍歷nums數(shù)組,不斷更新curSum和maxSum,最終得到最大子段和。
值得注意的是,在curSum小于0的時候,我們需要將其更新為當前遍歷到的數(shù)值,而不是保留前面的負數(shù)部分。
通過以上Java代碼,我們就能夠求解最大子段和問題。