Maximum Subarray Minimum Subarray

Given an array of integers, find a contiguous subarray which has the largest sum.

Have you met this question in a real interview? 

Yes

Example

Given the array [−2,2,−3,4,−1,2,1,−5,3], the contiguous subarray [4,−1,2,1] has the largest sum = 6.

Note

The subarray should contain at least one number.

Challenge

Can you do it in time complexity O(n)?

public class Solution {
    /**
     * @param nums: A list of integers
     * @return: A integer indicate the sum of max subarray
     */
    public int maxSubArray(ArrayList<Integer> nums) {
        // write your code
        if(nums == null || nums.size() == 0) return 0;
        int sum = 0, maxSum = Integer.MIN_VALUE;
        for(int i = 0; i < nums.size(); i++){
            sum += nums.get(i);
            maxSum = Math.max(sum, maxSum);
            if(sum < 0){
                sum = 0;
            }
        }
        return maxSum;
    }
}

Minimum Subarray

Given an array of integers, find the subarray with smallest sum.

Return the sum of the subarray.

Have you met this question in a real interview? 

Yes

Example

For [1, -1, -2, 1], return -3

Note

The subarray should contain at least one integer.

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

        

        if(nums == null || nums.size() == 0) return 0;

        int sum = 0, minSum = Integer.MAX_VALUE;

        for(int i = 0; i < nums.size(); i++){

            sum += nums.get(i);

            minSum = Math.min(sum, minSum);

            if(sum > 0){

                sum = 0;

            }

            

        }

        return minSum;

    }

}