題目

給定一個整數(shù)數(shù)組，找到一個具有最小和的子數(shù)組。返回其最小和。

** 注意事項(xiàng)
子數(shù)組最少包含一個數(shù)字 **

樣例
給出數(shù)組[1, -1, -2, 1]，返回 -3

分析

判斷加與不加的情況，這道題的解法很巧妙，類似于背包問題。
每個數(shù)組的元素都有兩種情況，加與不加，所以我們從第一個元素開始判斷，包括第一個元素時，和不包括第一個元素的情況取最小值，進(jìn)行判斷選擇。

代碼

public class Solution {
    /**
     * @param nums: a list of integers
     * @return: A integer indicate the sum of minimum subarray
     */
    public int minSubArray(ArrayList<Integer> nums) {
        // write your code
        int min_ending_here = nums.get(0);
        int min_so_far = nums.get(0);
        for(int i=1;i<nums.size();i++)
        {
            min_ending_here = Math.min(nums.get(i), nums.get(i)+ min_ending_here);
            min_so_far = Math.min(min_ending_here, min_so_far);
        }
        return min_so_far;
    }
}

最大子數(shù)組

這道題的思路和最小子數(shù)組是一樣的，只要更改判斷小為判斷大就可以了
這里就直接貼出代碼

public class Solution {
    /**
     * @param nums: A list of integers
     * @return: A integer indicate the sum of max subarray
     */
    public int maxSubArray(int[] nums) {
        // write your code
        int max_ending_here = nums[0];
        int max_so_far = nums[0];
        for( int i =1 ;i<nums.length; i++) {
            max_ending_here = Math.max( nums[i] , nums[i] + max_ending_here );
            max_so_far = Math.max( max_so_far, max_ending_here);
        }
        return max_so_far;
    }
}