package recursion;

import java.util.*;

import java.util.regex.Matcher;

import java.util.regex.Pattern;

public class AdvancedQuestions {

static Set<String> set = new HashSet<>();

public static void main(String[] args) {

// int a[][] = {{1, 1, 1, 1, 1, 1, 1, 1},

// {1, 1, 1, 1, 1, 1, 0, 0},

// {1, 0, 0, 1, 1, 0, 1, 1},

// {1, 2, 2, 2, 2, 0, 1, 0},

// {1, 1, 1, 2, 2, 0, 1, 0},

// {1, 1, 1, 2, 2, 2, 2, 0},

// {1, 1, 1, 1, 1, 2, 1, 1},

// {1, 1, 1, 1, 1, 2, 2, 1},

// };

// floodFill(a, 0, 0, 3, 1);

// printMatrix(a);

// permutations("abcc", 0, 3);

int a[] = {1, 5, 700, 2};

System.out.println(coinMax(a, 0, a.length-1));

}

static int coinMax(int a[], int l, int r) {

if(l+1 == r) {

return Math.max(a[l], a[r]);

}

return Math.max(a[l] + Math.min(coinMax(a, l+2, r), coinMax(a, l+1, r-1)),

a[r] + Math.min(coinMax(a, l+1, r-1), coinMax(a, l, r-2)));

}

static void permutations(String s, int l, int r) {

if(l == r) {

if(set.contains(s)) return;

set.add(s);

System.out.println(s);

return;

}

for(int i = l; i<=r; i++) {

s = interchangeChar(s, l, i);

permutations(s, l+1, r);

s = interchangeChar(s, l, i);

}

}

static String interchangeChar(String s, int a, int b) {

char array[] = s.toCharArray();

char temp = array[a];

array[a] = array[b];

array[b] = temp;

return String.valueOf(array);

}

static void floodFill(int a[][], int r, int c, int toFill, int prevFill) {

int rows = a.length;

int cols = a[0].length;

if(r < 0 || r >= rows || c < 0 || c >= cols) {

return;

}

if(a[r][c] != prevFill) {

return;

}

a[r][c] = toFill;

floodFill(a, r-1, c, toFill, prevFill);

floodFill(a, r, c-1, toFill, prevFill);

floodFill(a, r+1, c, toFill, prevFill);

floodFill(a, r, c+1, toFill, prevFill);

}

static void printMatrix(int a[][]) {

for(int[] array: a) {

for(int element: array) {

System.out.print(element +" ");

}

System.out.println();

}

}

}