0

Is anyone able to explain a reason why these two functions would have different outputs? I'm trying to memoize my recursive function, but it output a different value when I do. Any ideas why? Wouldn't that mean it would have to enter into the same subproblem and find a different answer for this to be returning something different? I'm super confused, thanks for any help

    public long maxAlternatingSumHelper(int[] nums,int index,boolean plus, long sum) {
        if (index == nums.length) {
            return sum;
        }
       
        int adder = nums[index];
        if (!plus) adder *= -1;
        long ans = Math.max(maxAlternatingSumHelper(nums,index+1,true, 0),
                Math.max(maxAlternatingSumHelper(nums,index+1,plus, sum),
                 maxAlternatingSumHelper(nums,index+1,!plus, sum + adder)));
        return ans;
    }

    Hashtable<IndexPlus,Long> sumDp = new Hashtable<>();
    public long maxAlternatingSumHelper(int[] nums,int index,boolean plus, long sum) {
        if (index == nums.length) {
            return sum;
        }
        if (sumDp.containsKey(new IndexPlus(index,plus))){
            return sumDp.get(new IndexPlus(index,plus));
        }
        int adder = nums[index];
        if (!plus) adder *= -1;
        long ans = Math.max(maxAlternatingSumHelper(nums,index+1,true, 0),
                Math.max(maxAlternatingSumHelper(nums,index+1,plus, sum),
                 maxAlternatingSumHelper(nums,index+1,!plus, sum + adder)));
        sumDp.put(new IndexPlus(index,plus),ans);
        return ans;
    }
Aris Emery
  • 19
  • 3
  • Can we see the implementation of IndexPlus? – Louis Wasserman Dec 13 '22 at 18:32
  • `IndexPlus` should have properly overridden methods `equals()` and `hashCode()` in order to server as a Key in a Map. Probably, forget to do that or there's some kind of flaw in the implementation of these methods. See [Why do I need to override the equals and hashCode methods in Java?](https://stackoverflow.com/questions/2265503/why-do-i-need-to-override-the-equals-and-hashcode-methods-in-java) – Alexander Ivanchenko Dec 13 '22 at 18:52
  • Also avoid using `Hashtable`, this class is obsolete. Use `HashMap` instead. – Alexander Ivanchenko Dec 13 '22 at 18:55

0 Answers0