0
import java.util.*;

public class ArrayList5 {

    static int max(ArrayList list) { // to be completed
        if (list.size() == 0) {
            return 0;
        }
        else
        {
            int first = (Integer) list.get(0);

            list.remove(0);
            if (first > max(new ArrayList(list)))
            {
                return first;
            } 
            else 
            {
                return max(list);
            }
        }

    }

    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList();
        Collections.addAll(list, 4, 5, 3, 2, 3, 1, 3);
        // int t=Console.readInt("Enter Target:");
        int res1 = max(new ArrayList(list));
        System.out.println("max=" + res1);
    }
}

I don't understand why the max(new ArrayList(list))) part is required. Why does it have to create a new one and why can't it continue to work with the one list?

Also why doesn't it get caught in a loop (it's recursion so it will keep sending up a new list so I don't understand why 'first' isn't going to be 4 every time)?

JWick
  • 15
  • 4
  • 1
    This is a *very* inefficient implementation. – Oliver Charlesworth May 02 '18 at 23:27
  • I didn't make it. It's notes from a college class. The point of it is to gain an understanding in recursion with array lists – JWick May 02 '18 at 23:29
  • 1
    Well it is required because the implementation calls the recursion at two points, and the list passed as parameter is consumed (i.e. it will be empty when the recursion terminates). It would be more efficient to calculate the max of the rest once, and use it in both cases: `int max = max(list); if (first > max) { ... } else { ... }`. On a sidenote: this implementation only works correct, if the `max` of the list is `>= 0`. – Turing85 May 02 '18 at 23:29
  • I get that there's better ways of doing it. But I'm trying to understand why it works as it is. That second if condition is throwing me a lot – JWick May 02 '18 at 23:31
  • Is it the `if` throwing you off or the `new ArrayList(list)`? – Turing85 May 02 '18 at 23:33
  • The new `ArrayList(list)` . Basically it works, but I can't figure out why it works – JWick May 02 '18 at 23:35
  • You know that [Java is always pass-by-value](https://stackoverflow.com/questions/40480/is-java-pass-by-reference-or-pass-by-value) and know what this means for reference-types I presume. You start by assuming that the first element in the list is the maximum. You remove the first element from the list (`list.remove(0)`) and determine the maximum of the rest of the list (`max(list)`). Problem is: the `list` you pass in will be empty afterwards and since you need the call to `max(...)` TIWCE, you need to clone the list for the first call (`max(ArrayList(list))`). – Turing85 May 02 '18 at 23:38
  • This `list.remove(0); ... new ArrayList(list)` basically produces a sublist which starts with the second element. – lexicore May 02 '18 at 23:40
  • @Turing85 this may be where I was going wrong. So when I clone the list, it clones by reference yes? So that's why it won't include the 4 (the original first value removed)? – JWick May 02 '18 at 23:41
  • The first element is not included because you removed it before cloning (`list.remove(0);`). The call `new ArrayList(list)` creates a real clone in this case: an indepentent list that can be independently modified from the original list. – Turing85 May 02 '18 at 23:42
  • @lexicore Careful. Sublists are views and changes to views are carried through to the underlying list. – Turing85 May 02 '18 at 23:44
  • @Turing85 perfect. Thanks very much – JWick May 02 '18 at 23:48
  • If you are able to fix the bug I mentioned earlier, your understanding of this algorithm should be sufficient. – Turing85 May 02 '18 at 23:58

2 Answers2

1

Actually, there is a lot of superfluous code that is not required and make the code cumbersome/more difficult to read/understand.

You can simplify the code a lot and get rid of any reference to ArrayList which are not really necessary and by using proper generic at the right places, make the code actually readable.

You don't need to cast or create list all over the place.

public class ArrayList5 {

    static int max(final List<Integer> list) {
        if(list.isEmpty()) return 0;

        final int head = list.get(0);
        final List<Integer> tail = list.subList(1, list.size());

        return (head > max(tail)? head:max(tail));
    }

    public static void main(final String... args) {
       final int res1 = max(Arrays.asList(4, 5, 3, 2, 3, 1, 3));
       System.out.printf("max=%d", res1);
    }
}
Turing85
  • 18,217
  • 7
  • 33
  • 58
clement
  • 1,491
  • 2
  • 10
  • 11
  • "*`if(list.isEmpty()) return 0;`*" - Don't do that. We dont have to fight for some KB HDD space. Write the parentheses and write the linebreaks. --- You still have the bug that `max(...)` only works if the maximum is `>= 0`. – Turing85 May 03 '18 at 00:04
  • where is list modified? – clement May 03 '18 at 00:05
  • I am not changing the basic code, just rewrote it in a different way, not trying to fix it, trying to show how it works in a clearer way. Also, I never put curly braces for my early returns, it keeps them short and clear - question of preference. Don't think that deserve a downvote, but whatever :) – clement May 03 '18 at 00:07
0

You should try this:

static int max(ArrayList<Integer> list) {...}
public static void main(String[] args) {
    ArrayList<Integer> list = new ArrayList();
    Collections.addAll(list, 4, 5, 3, 2, 3, 1, 3);
    // int t=Console.readInt("Enter Target:");
    int res1 = max(new ArrayList(list));
    System.out.println("max=" + res1);
}

The compiler is probably throws a warning because you don't declare the type of the ArrayList.

Mike Bean
  • 3
  • 5