0
$\begingroup$

This question is already asked:

To find a subsequence having largest sum among n positive integers by not choosing 3 consecutive elements

https://stackoverflow.com/questions/29249104/maximum-sum-in-ipl-matches

Problem Statement: https://www.codechef.com/ZCOPRAC/problems/ZCO14004/

Bonus/Similar link: https://discuss.codechef.com/questions/55874/iplzco-2014

Prerequisite: I am beginner in dynamic programming and algorithm.

As I understand till now solving a problem via dynamic programming require breaking into sub-problems and reusing the result of the problem solved.

The problem is solved via DP based on the comment and answers on various links related to the same context.

There is a complete & working solution for the problem :

SOURCE OF SOLUTION

    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int arr[] = new int[n];
    for (int i = 0; i < n; i++) {
        arr[i] = sc.nextInt();
    }
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum = sum + arr[i];

    int min[] = new int[n];
    min[0] = arr[0];
    min[1] = arr[1];
    min[2] = arr[2];
    for (int i = 3; i < n; i++)
        min[i] = arr[i] + minimum(min[i - 1], min[i - 2], min[i - 3]);

    int val = sum - minimum(min[n - 1], min[n - 2], min[n - 3]);
    System.out.println(val);

Note: function minimum(a, b, c) returns minimal number of parameters passed.

I don't understand how this solution works (Proof of solution). How does it break into subproblems and compute result (if it is DP)?

How should we propose the solution of the problem via DP (if possible)?


SOURCE: ANOTHER SOLUTION

Let $X_k$ be the largest sum up to the k-th element that follows the rules and doesn't include the k-th element itself. Let $Y_k$ be the largest sum up to the k-th element that follows the rules and includes the k-th element itself, but not the one before. Let $Z_k$ be the largest sum up to the k-th element that follows the rules and includes the k-th element itself, and the one before as well. Let $a_k$ be the array elements. Then $X_{k+1} = max (X_k, Y_k, Z_k)$, $Y_{k+1} = X_k + a_{k+1}$, and $Z_{k+1} = Y_k + a_{k+1}$. Start with $X_0 = Y_0 = Z_0 = 0$, calculate $X_n, Y_n, Z_n$ and the solution is $max (X_n, Y_n, Z_n)$.

How this solves the problem/works/breakdowns-into-subproblem?

$\endgroup$
  • $\begingroup$ Please make your question self-contained, so we can understand your question and the problem statement without having to click on a link (and so the question continues to make sense even if the link stops working). $\endgroup$ – D.W. Dec 12 '17 at 3:19
  • 1
    $\begingroup$ I don't understand what you are asking. What do you mean by "How should we propose the solution of the problem?" Are you asking for an algorithm that uses dynamic programming? If so, looks like the solutions you already have can be considered dynamic programming algorithms. Most importantly: Have you tried to solve it yourself? See here for more resources on how to design a dynamic programming algorithm. Maybe you should practice with simpler dynamic programming problems first, to get the basic idea. $\endgroup$ – D.W. Dec 12 '17 at 3:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.