You are given an array full of positive integers. Write a function that returns the largest sum you can get by adding together numbers in non-adjacent indices from the array. I.e. you if you include the things stored in arr[i] in your sum, you can't include what is stored in arr[i-1] or arr[i+1]

Question

You are given an array full of positive integers.  Write a function that returns the largest sum you can get by adding together numbers in non-adjacent indices from the array. I.e. you if you include the things stored in arr[i] in your sum, you can't include what is stored in arr[i-1] or arr[i+1]

john doe · Accepted Answer

public static int subsetSumNoAdj(int[] a, int end) {
		if (end < 2) {
			return a[end];
		}
		return Math.max(a[end] + subsetSumNoAdj(a, end - 2), subsetSumNoAdj(a,
				end - 1));
	}

Meta

Pergunta de entrevista da empresa Meta

Resposta da entrevista

Empresas seguidas

Buscas de vagas