public static int dfs(int num, int sumGreedy, int sum, int indexIzq, int indexDer, int turn, String cadSum, String cadgreedy) {

		if (indexIzq <= indexDer) {
			if (turn == 0) {
				if (arr[indexIzq] >= arr[indexDer]) {
					if (dp[indexIzq][indexDer] != Integer.MIN_VALUE) {
						value = (sum - (sumGreedy + arr[indexIzq]));
						dp[indexIzq][indexDer] = Math.max(dp[indexIzq][indexDer], value);

					} else
						dp[indexIzq][indexDer] = dfs(num + 1, sumGreedy + arr[indexIzq], sum, indexIzq + 1, indexDer, 1, cadSum,
								cadgreedy + arr[indexIzq] + " ");
				} else {
					if (dp[indexIzq][indexDer] != Integer.MIN_VALUE) {
						value = (sum) - (sumGreedy + arr[indexDer]);
						dp[indexIzq][indexDer] = Math.max(dp[indexIzq][indexDer], value);
					} else {
						dp[indexIzq][indexDer] = dfs(num + 1, sumGreedy + arr[indexDer], sum, indexIzq, indexDer - 1, 1, cadSum,
								cadgreedy + arr[indexDer] + " ");
					}

				}
			} else {
				if (arr[indexIzq] >= arr[indexDer]) {
					dfs(num + 1, sumGreedy, sum + arr[indexIzq], indexIzq + 1, indexDer, 0, cadSum + arr[indexIzq] + " ",
							cadgreedy);
					dfs(num + 1, sumGreedy, sum + arr[indexDer], indexIzq, indexDer - 1, 0, cadSum + arr[indexDer] + " ",
							cadgreedy);
				} else {
					dfs(num + 1, sumGreedy, sum + arr[indexDer], indexIzq, indexDer - 1, 0, cadSum + arr[indexDer] + " ",
							cadgreedy);
					dfs(num + 1, sumGreedy, sum + arr[indexIzq], indexIzq + 1, indexDer, 0, cadSum + arr[indexIzq] + " ",
							cadgreedy);

				}

			}
		}
		if (sum - sumGreedy > max && indexIzq >= indexDer) {
			max = sum - sumGreedy;
			camino = cadSum + "    " + cadgreedy;
		}
		return sum - sumGreedy;
	}