對于一串整數序列,我們希望求出其中最小的子序列和,Java提供了一種高效的解決方案。
public static int minSubArray(int[] nums) { int minSum = Integer.MAX_VALUE; int curSum = 0; for (int num : nums) { curSum += num; minSum = Math.min(minSum, curSum); curSum = Math.min(curSum, 0); } return minSum; }
這個算法的思路是遍歷整個序列,維護當前的子序列和和最小子序列和,同時不斷更新它們。具體來說,我們用一個變量curSum記錄當前的子序列和,用一個變量minSum記錄出現過的最小子序列和。
對于每個數num來說,如果將它加入curSum后會使得curSum變得更小,那么就可以考慮拋棄curSum之前的所有數,從num開始重新計算curSum。同時,也需要及時更新minSum,使得其保持最小值。
這個算法的時間復雜度是O(n),其中n是整數序列的長度,因此非常高效。這個算法的代碼也非常簡潔,使用Java編寫起來非常方便。