Geek asks and answers

Maximum amount in a restricted array

I have this problem, when an array of positive numbers is given, I have to find the maximum amount of elements, so that two adjacent elements will not be selected. The maximum should be less than a certain predetermined K. I tried to think about the lines of a similar problem without k, but still have not succeeded. I have the following dp-ish soln for the last problem

    int sum1,sum2 = 0;
    int sum = sum1 = a[0];

    for(int i=1; i<n; i++)
    {
        sum = max(sum2 + a[i], sum1);
        sum2 = sum1;
        sum1 = sum;
    }

Can someone give me advice on how to continue my current problem?

+3
source share
4 answers

The best I can think of with my head is O (n * K) dp:

int sums[n][K+1] = {{0}};
int i, j;
for(j = a[0]; j <= K; ++j) {
    sums[0][j] = a[0];
}
if (a[1] > a[0]) {
    for(j = a[0]; j < a[1]; ++j) {
        sums[1][j] = a[0];
    }
    for(j = a[1]; j <= K; ++j) {
        sums[1][j] = a[1];
    }
} else {
    for(j = a[1]; j < a[0]; ++j) {
        sums[1][j] = a[1];
    }
    for(j = a[0]; j <= K; ++j) {
        sums[1][j] = a[0];
    }
}
for(i = 2; i < n; ++i) {
    for(j = 0; j <= K && j < a[i]; ++j) {
        sums[i][j] = max(sums[i-1][j],sums[i-2][j]);
    }
    for(j = a[i]; j <= K; ++j) {
        sums[i][j] = max(sums[i-1][j],a[i] + sums[i-2][j-a[i]]);
    }
}

sums[i][j]contains the maximum amount of non-adjacent elements a[0..i], not exceeding j. Then the decision will be sums[n-1][K]at the end.

+3
source
  • (A2) (A1).
  • (A2).
  • (A3).
  • (A3).
  • , k. , .
  • , (A2), ( 3) 3.
  • , (.. , 1 + k), (A1) 0.
  • - (, k), null, .
0

:

" ".

, K.

, , , K

: , ...

0

"k", : fooobar.com/questions/269212/...

The above solution, in my opinion, can be easily extended to have a k constraint by simply changing the if condition in the following for the loop to include the constraint: possibleMax <k

// Subproblem solutions, DP
for (int i = start; i <= end; i++) {
    int possibleMaxSub1 = maxSum(a, i + 2, end);
    int possibleMaxSub2 = maxSum(a, start, i - 2);

    int possibleMax = possibleMaxSub1 + possibleMaxSub2 + a[i];
    /*
    if (possibleMax > maxSum) {
        maxSum = possibleMax;
    }
    */
    if (possibleMax > maxSum && possibleMax < k) {
        maxSum = possibleMax;
    }
}

As indicated in the source link, this approach can be improved by adding memorization so that the solutions of the repeating routines are not recounted. Or it can be improved using a dynamic bottom-up approach (the current approach is a recursive top-down approach)

You can refer to the bottom-up approach: fooobar.com/questions/269212 / ...

0
source

More articles:


All Articles