Sunday 7 January 2024

 longest Subarray with maximum sum as k

import java.util.*;

public class MyFirstClass {

    public static void main(String[] args) {

        int[] a = {2, 3, 1, 1, 2, 4, 2, 9};

        long k = 10;

        int len = getLongestSubarray(a, k);

        System.out.println("The length of the longest subarray is: " + len);

    }

public static int getLongestSubarray(int []a, long k) {

        int n = a.length; // size of the array.

        Map<Long, Integer> preSumMap = new HashMap<>();

        long sum = 0;

        int maxLen = 0;

        for (int i = 0; i < n; i++) {

            //calculate the prefix sum till index i:

            sum += a[i];


            // if the sum = k, update the maxLen:

            if (sum == k) {

                maxLen = Math.max(maxLen, i + 1);

            }


            // calculate the sum of remaining part i.e. x-k:

            long rem = sum - k;


            //Calculate the length and update maxLen:

            if (preSumMap.containsKey(rem)) {

                int len = i - preSumMap.get(rem);

                maxLen = Math.max(maxLen, len);

            }


            //Finally, update the map checking the conditions:

            if (!preSumMap.containsKey(sum)) {

                preSumMap.put(sum, i);

            }

        }


        return maxLen;

    }

}


No comments:

Post a Comment

Good thoughtful question on Binary search on answers

Problem link:  https://leetcode.com/problems/maximize-score-of-numbers-in-ranges/description/ Solution: //import java.util.Arrays; class So...