#Problem

#⭐️⭐️⭐️⭐️⭐️

求一个array, 如果可以循环的话, 非相邻元素能组成的最大sum.

#Solution

Dynamic Programming

[0, n - 2] 做一遍dp.
[1, n - 1] 做一遍dp.

#Code

#Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public int maxCircularSumWithoutAdjacentElements(int[] A) {
if (A.length == 1) return A[0];
if (A.length == 2) return Math.max(A[0], A[1]);
int n = A.length;
int max1 = maxSumWithoutAdjacentElements(A, 0, n - 2);
int max2 = maxSumWithoutAdjacentElements(A, 1, n - 1);
return Math.max(max1, max2);
}
private int maxSumWithoutAdjacentElements(int[] A, int start, int end) {
if (start == end) return A[start];
if (end - start == 1) return Math.max(A[start], A[end]);
int n = end - start + 1;
int[] dp = new int[n];
int res = Integer.MIN_VALUE;
for (int i = start + 2; i <= end; i++) {
dp[i] = A[i];
dp[i] = Math.max(dp[i], dp[i - 2] + A[i]);
dp[i] = Math.max(dp[i], dp[i - 1]);
res = Math.max(res, dp[i]);
}
return res;
}
}

Comments