Minimum Subarray Of Sumk

Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray [numsl, numsl+1, ..., numsr-1, numsr] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2 

Explanation: The subarray [4,3] has the minimal length under the problem constraint. 

public class MinimumSubarrayOfSumk {

    public static void main(String[] args) {

        int[] arr = {

                10,5,13,4,8,4,5,11,14,9,16,10,20,8};

        int target  =80;

        int i =-1;

        int j=-1;

        int sum = 0;

        int length = Integer.MAX_VALUE;

        while (true){

        boolean f1 = false,f2 = false;

            while (i<arr.length-1 && sum<target){

                f1 = true;

                i++;

                sum+=arr[i];

                if(sum>=target){

                    length = Math.min(length,i-j);

                    break;

                }

               // f1 = true;

            }

            while (j<i && sum>=target){

                f2 = true;

                j++;

                sum-=arr[j];

                if(sum>=target){

                    length = Math.min(length,i-j);

                }else{

                    break;

                }

               // f2 = true;

            }

            if(!f1 && !f2){

                break;

            }

        }

        System.out.println(length);

    }

}

Result: 6

Maximum Product Subarray

 Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4], the contiguous subarray [2,3] has the largest product = 6.

public class MaximumProductSubArray {

    public static void main(String[] args) {

        int[] arr = {-2,1,-4};

        int result = arr[0];

        int max = arr[0];

        int min = arr[0];

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

          int  tempMax = Math.max(arr[i], Math.max(max*arr[i],min*arr[i]));

          min = Math.min(arr[i], Math.min(max*arr[i],min*arr[i]));

          max = tempMax;

          result = Math.max(result,max);

        }

        System.out.println(result);

    }

}

Result:8

Maximum Subarray

 Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [ − 2,1, − 3,4, − 1,2,1, − 5,4], the contiguous subarray [4, − 1,2,1] has the largest sum =

6.

public class MaximumSumSubarray {

    public static void main(String[] args) {

        int[] arr = {4,3,-2,6,-14,7,-1,4,5,7,-10,2,9,-10,-5,-9,6,1};

        int maxSum =Integer.MIN_VALUE;

        int tempSum = 0;

        for(int i = 0;i< arr.length;i++){

            tempSum+=arr[i];

            if(tempSum<arr[i]){

                tempSum = arr[i];

            }

            maxSum = Math.max(maxSum,tempSum);

        }

        System.out.println(maxSum);

    }

}

Result: 23

Subarray Sum Equals K

 Given an array of integers and an integer k, find the total number of continuous subarrays whose sum equals to

k.

Example 1:

Input:nums = [1,1,1], k = 2 Output: 2

Note that empty array is not considered as a subarray.

public class CountSubarraySumEqualsK {

    public static void main(String[] args) {

        int arr[] = {3,9,-2,4,1,-7,2,6,-5,8,-3,-7,6,2,1};

        //int arr[] = {1,1,2};

        Map<Integer,Integer> map= new HashMap<>();

        int sum = 0;

        int count = 0;

        int k = 5;

       // int k =2;

        for(int i = 0;i<arr.length;i++){

            sum+=arr[i];

            if(sum==k){

                count++;

            }

            int diff = sum-k;

            if(map.containsKey(diff)){

                count = count + map.get(diff);

            }

            if(map.containsKey(sum)){

                map.put(sum,map.get(sum)+1);

            }else{

                map.put(sum,1);

            }

        }

        System.out.println(count);

    }

}

Result: 7

Maximum Size Subarray Sum Equals k

 Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isn’t

one, return 0 instead.

Note: The sum of the entire nums array is guaranteed to fit within the 32-bit signed integer range.

Example 1: Given nums = [1, -1, 5, -2, 3], k = 3, return 4. (because the subarray [1, -1, 5, -2] sums to 3 and is the

longest)

public class MaxSizeSubArraySumK {

    public static void main(String[] args) {

        int arr[] = {2,1,-1,3,5,2,-5,1,-3};

        int k = 3;

        int max = 0;

        int sum = 0;

        Map<Integer, Integer> map = new HashMap<>();

        for(int i = 0;i<arr.length;i++){

            sum+=arr[i];

            if(sum==k){

                max = Math.max(max,i);

            }

            int diff = sum-k;

            if(map.containsKey(diff)){

                max= Math.max(max,i-map.get(diff));

            }

            if(!map.containsKey(sum)){

                map.put(sum,i);

            }

        }

        System.out.println(max);

    }

result: 8