首页 > itarticle > 数组不相邻数最大求和

数组不相邻数最大求和

admin 11月 11, 2020 0

题目

给定一个整数的数组，相邻的数不能同时选，求从该数组选取若干整数，使得他们的和最大

思路

in（i）:表示包含arr[i]的最大值
ex（i）：表示不包含arr[i]的最大值
in(i)=ex(i-1)+arr[i];
ex(i)=max[in(i-1),ex(i-1)];

代码

public static int (int[] arr) {
		if (arr == null || arr.length == 0)
			return 0;
		int inI=arr[0];int exI=0;
		for (int i = 1; i < arr.length; i++) {
			int inn=exI+arr[i];
			exI=Math.max(inI, exI);
			inI=inn;
		}
		return Math.max(exI, inI);
	}