CODEWITHSUNDEEP
c++arraysalgorithmnumber-theory
user13217404
user13217404

Reputation:

Maximize the summation Operation

Given an array of n numbers and integer k and m. We have to select subsequence of length k of the array. given a function s = summation from i=1 to i=k A(i)*(i mod m). We have to maximise s.

Constraints

n<10000

k<1000

|A(i)| < 10000000

m<10000000

Suppose array is 4 9 8 2 6 7 4. And k is 4 and m is 3. For this case answer is 32. ( 9*1 + 8*2 + 2*0 + 7*1 )

My code:

#include<bits/stdc++.h>
using namespace std;

#define ll long long int
#define g_long        long long
#define maxx(a, b) a > b ? a : b

int main()
{
    ll n, k, m, i, j;
    cin >> n >> k >> m;

    ll arr[n + 1] =
    { 0 };

    for (i = 0; i < n; i++)
    {
        cin >> arr[i];
    }

    ll data[8][8] =
    { 0 };
    for (i = 1; i <= k; ++i)
    {
        for (j = 1; j <= 7; ++j)
        {
            ll ans = maxx((data[i - 1][j - 1] + (arr[j - 1] * (i % m))),
                    (data[i][j - 1]));
            data[i][j] = ans;
        }
    }

    cout << data[k][n];
}

My approach is to first generate a subsequence of length k than keep on updating maximum value. This code passes some of the test cases but some are giving wrong answer.

Can anyone help me what I am doing wrong in my code or suggest a better approach for this question?

Upvotes: 0

Views: 220

Answers (1)

Yash Shah
Yash Shah

Reputation: 1654

The 2-D Dimensional Dp table which we are going to form by the following observation:

We have to take the maximum between the two values: (dp[i-1][j-1]+(arr[j-1]*(i%m)),dp[i][j-1])

where arr is the array i.e. [4 9 8 2 6 7 4] and dp is 2-dimensional DP-Table.

DP Table is given with rows as values of k (from 0 to k) and with columns as elements of the array.

DP| 0 | 4 | 09 | 08 | 02 | 06 | 07 | 04

00 || 0 | 0 | 00 | 00 | 00 | 00 | 00 | 00

01 || 0 | 4 | 09 | 09 | 09 | 09 | 09| 09

02 || 0 | 0 | 22 | 25 | 25 | 25 | 25| 25

03 || 0 | 0 | 00 |22 | 25 | 25 | 25| 25

04 || 0 | 0 | 00 |00 | 24 | 26 | 32 | 32

The following python code passes all the test cases as discussed in comments:

n = 7
k = 4 
m = 3
arr = [49999, 4999, 4999, 4999, 99999, 99999, 49999]

# Initialising 2-D DP with 0 of size (k+1)*(n+1) 
# Extra rows for handling edge cases
dp = [[0 for i in range(n+1)] for j in range(k+1)] 

for i in range(1,k+1):
    for j in range(i,n+1):
        ans = max(dp[i-1][j-1]+(arr[j-1]*(i%m)),dp[i][j-1])
        dp[i][j] = ans

# Maximum element at the bottom-right-most of 2-D DP
print(dp[k][n])

Thanks to @MBo for sharing top-down approach...

@functools.lru_cache
def mx(i, k):
  if (i < 0 or k == 0):
    return 0
  else:
    return max(mx(i-1, k), (mx(i-1, k-1) + l[i]*(k%m)))

Upvotes: 2

Related Questions