Find a recurrence relation for the following problem in terms of smaller subprob

Question

Find a recurrence relation for the following problem in terms of smaller subproblems: Given an array A of integers and a number target, what is the size of the largest subset of A whose sum is less than or equal to target? For example, if A = [2, 5, 5, 2] and target = 10, then the answer is 3 because although the subset 5, 5 sums to 10 and the subset 2, 5, 2 sums to 9, the second solution has corresponds to a subset of size 3 rather than 2. (Include the base case. You may give your answer in math notation, code or pseudocode. Solve the general problem, not just the example.)

Explanation / Answer

Code with output:

package my.change;

//A Java program to find maximum length subarray with target sum
import java.util.HashMap;

public class MaxLenSumSub {

   // Returns length of the maximum length subarray
   public static int maxSubArrayLen(int[] nums, int k) {
       int sum = 0, max = 0;
       HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
       for (int i = 0; i < nums.length; i++) {
           sum = sum + nums[i];
           if (sum == k)
               max = i + 1;
           else if (map.containsKey(sum - k))
               max = Math.max(max, i - map.get(sum - k));
           if (!map.containsKey(sum))
               map.put(sum, i);
       }
       return max + 1;
   }

   // Drive method
   public static void main(String arg[]) {
       int arr[] = { 2, 5, 5, 2 };
       int sum = 10;
       System.out.println("Length of the longest subarray is " + maxSubArrayLen(arr, sum));
   }
}

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.