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

Max Sum Contiguous Subarray

public class Solution {
    public int maxSubArray(final List<Integer> A) {
        int tempSum=0;
        int maxSum = Integer.MIN_VALUE;
            for(int j=0;j<A.size();j++){
                tempSum +=A.get(j);
                if(tempSum>maxSum){
                    maxSum = tempSum;
                }
                if(tempSum<0){
                    tempSum=0;
                }
               
            }
            return maxSum;
    }
}

find max sub array program

Program1: find sum of maxSubArray

 public int maxSubArray(final int[] A) {
     int largestSum = Integer.MIN_VALUE;
        int tempSum = 0;
        for(int i=0;i<A.length;i++) {
            if(tempSum+A[i]<A[i]) {
                tempSum = A[i];
            }else {
                tempSum = tempSum+A[i];
            }
           
            if((tempSum>Integer.MIN_VALUE && tempSum>largestSum) || tempSum>0) {
                 if(largestSum<tempSum){
                    largestSum = tempSum;
                
                    }
            }else {
                tempSum=0;
            }
        }
        return largestSum;
    }


intput:{-2,1,-3,-4,-1,-2,-1,-7,-5,-4}

output: 1


innput:{-160,-20,-10}
output -10

input: -160,-20,-10,1,2
output: 3



Program2: find sum of maxSubArray with start and end index

public static void findMaxSumSubArray(int[] arr) {
        int largestSum = Integer.MIN_VALUE;
        int tempSum = 0;
        int startIndex = 0;
        int endIndex = 0;
        int s = 0;
        for(int i=0;i<arr.length;i++) {
            if(tempSum+arr[i]<arr[i]) {
                tempSum = arr[i];
            }else {
                tempSum = tempSum+arr[i];
            }
           
            if((tempSum>Integer.MIN_VALUE && tempSum>largestSum) || tempSum>0) {
                 if(largestSum<tempSum){
                     endIndex = i;
                     startIndex = s;
                    largestSum = tempSum;
               
                    }
            }else {
                s = i+1;
                tempSum=0;
            }
        }
        System.out.println("index start::"+startIndex +" and end: "+endIndex);
        System.out.println("sum::"+largestSum);
    }

Find maximum sub array of positve number

 public int[] maxset(int[] A) {
       
        long tempSum = 0;
        long finalSum = 0;
        ArrayList<Integer> maxArray = new ArrayList<>();
        ArrayList<Integer> newArray = new ArrayList<>();
 
        for(int i=0;i<A.length;i++) {
            if(A[i]>=0){
                tempSum = tempSum+A[i];
                newArray.add(A[i]);
          
                if(tempSum>finalSum ||( tempSum==finalSum && newArray.size()>maxArray.size())) {
                    finalSum = tempSum;
                    maxArray = (ArrayList<Integer>)newArray.clone();
                    
                }
            }else {
                tempSum = 0;
                 newArray = new ArrayList<>();
                        
            }
        }
       
        int[] list = new int[maxArray.size()];
        for(int i=0;i<maxArray.size();i++) {
            list[i] = maxArray.get(i);
        }
       
        return list;
       
   
    }

input:  int[] arr = {1967513926, 1540383426, -1303455736, -521595368};
output: [1967513926, 1540383426]

input: int[] arr = {0,0,-1,0}
output: [0,0]