LintCode ×îС×ÓÊý×é && ×î´ó×ÓÊý×éÌâÄ¿·ÖÎö´úÂë×î´ó×ÓÊý×é

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;
    }
}

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;
    }
}