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

Notice

The subarray should contain at least one number.

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.

if we know the first i item, then the i + 1 is either include i + 1 item or not. and then we keep a global

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
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int max = nums[0];
        int currentMax = nums[0];


        for (int i = 1; i < nums.length; i++) {

            currentMax = Math.max(nums[i], currentMax + nums[i]);
            max = Math.max(currentMax, max);
        }
        return max;
    }

}

sort two list and merge

public int[] intersection(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);

        int i = 0, j = 0;
        int[] temp = new int[nums1.length];
        int index = 0;
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] == nums2[j]) {
                if (index == 0 || temp[index - 1] != nums1[i]) {
                    temp[index++] = nums1[i];
                }
                i++;
                j++;
            } else if (nums1[i] < nums2[j]) {
                i++;
            } else {
                j++;
            }
        }

        int[] result = new int[index];
        for (int k = 0; k < index; k++) {
            result[k] = temp[k];
        }

        return result;
    }

hashmap

public int[] intersection(int[] nums1, int[] nums2) {
        // Write your code here
        if (nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0) {
            return new int[0];
        }

        HashSet<Integer> hash = new HashSet<>();
        for (int i = 0; i < nums1.length; i++) {
            hash.add(nums1[i]);
        }

        HashSet<Integer> result = new HashSet<>();

        for (int i = 0; i < nums2.length; i++) {
            if (hash.contains(nums2[i]) && !result.contains(nums2[i])) {
                result.add(nums2[i]);
            }
        }

        int[] ans = new int[result.size()];
        int i = 0;
        for (Integer item : result) {
            ans[i] = item;
            i++;
        }

        return ans;

    }