How to solve DP problems with pattern ?

1. Subset Sum (Non-continuous) [Knapsack problem]

Now, At last I will tell you to solve three different problems based on subarray and sum. We will solve three problem with one solution (Sliding Window Approach).

1. Indexes of subarray with given sum K
2. Count of subarrays having sum K https://leetcode.com/problems/subarray-sum-equals-k/
3. Max length of subarray having sum K https://www.codingninjas.com/codestudio/problems/longest-subarray-with-sum-k_5713505

package array.subArrayAndSum;

public class SubArrayWithSumK {

    public static void main(String[] args) {
        int[] array = {1,4,3,2,1,1,1,1,1};
        int K = 5;

        int i = 0;
        int j = 0;
        int currSum = 0;

        int count = 0;
        int maxLength = Integer.MIN_VALUE;

        while(j < array.length){
            currSum += array[j];

            if(currSum < K){
                j++;
            }

            if(currSum > K){
                while (currSum > K){
                    currSum -= array[i];
                    i++;
                }
                j++;
            }

            if(currSum == K){
                count++;
                maxLength = Math.max(maxLength,j-i+1);
                System.out.println("SUbarray found between indexes "+ i + " and "+j);
                j++;
            }
        }

        System.out.println("Total subarray Count "+count);
        System.out.println("Subarray MaxLength "+maxLength);
    }
}

with small tweaks we can also solve below problems :

1. Continuous subarray sum https://leetcode.com/problems/continuous-subarray-sum/

2. Subarray Product Less Than K https://leetcode.com/problems/subarray-product-less-than-k/

Thanks for reading. I will kepp updating this blog as I get some more intresting problems. Happy Learning !!