This is the question I'm dealing with: http://codeforces.net/problemset/problem/327/A
I'm trying to practice dynamic programming, and this is the code that I have came up.
#include <bits/stdc++.h>
using namespace std;
const int maxN = 100;
int a [maxN + 5], dp [maxN + 5];
int main ()
{
int n;
scanf ("%d", &n);
int ans = 0;
for (int i = 0; i < n; i++)
{
scanf ("%d", &a [i]);
if (a [i] == 1)
ans++; // get how many 1s are in the numbers
}
for (int i = 0; i < n; i++)
{
dp [i] = 0; // set to 0 since we're getting max
for (int j = i; j < n; j++)
{
int count = 0;
for (int k = i; k <= j; k++)
{
if (a [k] == 1)
count -= a [k];
else
count += 1;
} // basically, if we have more zero than ones, we would choose it.
dp [i] = max (count, dp [i]);
}
if (i > 0)
dp [i] = max (dp [i], dp [i - 1]);
}
if (ans == n)
ans--;
printf ("%d\n", ans + dp [n - 1]);
return 0;
}
Though it got accepted, I feel like this isn't the efficient way? So, what is the correct way of doing such dp problem?
Your approach seems fine except that a lot a lot of waste iterations are being carried out here...The third loop that uses 'k' isin't required I guess...just use a prefix sum array...A prefix sum array is many a times used to solve dynamic programming questions... My code Here...
-If u'd like to know more about using arrays for solving DP questions , my favourite question is: DZY loves sequences..
can you explain your usage of prefix sum for this problem?
consider the range i...j .the sum of this range is the number of 1's in this range...so the number of 0's in this range =(size of range-sum of range)....number of 1's outside this range =(total_sum-sum of this range.). So max=Math.max(max,number of 1's outside this range+number of zeros that can be flipped in this range).
for reference since this is a DP exercise, you can also formulate this problem in another way, while achieving the same time complexity (n^2).
focus on a segment of your array defined by indices i...j, and define dp[i][j] to store the optimal solution for that segment (this solution basically refers to the maximum number of 1s that can be achieved when you apply exactly one move in the segment).
How can you find the optimal solution for i....j if you know the optimal solutions for all the small sub problems?
Try all possibilities.
Case 1: Flip everything from i to j. So dp[i][j] = sum of all 1s achieved from i to j. Use the prefix sum approach to find each sum in constant time. Otherwise if you do it like in your code the time complexity will be n^3.
Case 2: Do not flip i, so dp[i][j] = data[i] + dp[i+1][j]
Case 3: Do not flip j, so dp[i][j] = data[j] + dp[i][j-1]
Case 4: Do not flip j AND do not flip i, so dp[i][j] = data[i] + data[j] + dp[i+1][j-1]
The final answer will be stored in dp[0][n-1].
With some care about the corner cases you can achieve a correct implementation.
is there another way that you can think of that can achieve a fewer complexity?
Yes. In fact as also explained in the tutorial you can do it in O(n) time while only using O(n) space. The tutorial refers to a reduction to another problem which they call "maximum subsequence", however that is not very correct and I will elaborate more here.
Focus on your input, let's say you store it in an array called
A. This array will initially consist of zeros and ones.Now focus on a move. Let us try to understand what a move really does. A move is executed on a segment (or subarray) of
Adefined by some left indexiand some right indexj. When you apply a move on this segment all its elements are flipped. We want to find that segment, or subarray, defined byi,jsuch that if a move is applied, then the total number of ones inAis maximized.Having understood exactly what this problem is asking us to do, we can now change the formulation a little bit. When we make a move and change some 0 to 1, we get a
gainof 1. A gain basically refers to the fact that you just managed to create a 1, and 1s are good since the more you have, the better the score of the corresponding move. If we change some 1 to 0, we get a gain of -1 respectively. Now letGbe some array for which initially we haveG[i] = 1ifA[i] = 0andG[i] = -1ifA[i] = 1.Suppose that you can somehow find the subarray of
Gthat achieves the maximum overall gainx. And letybe the number of 1s that you originally have inA. The optimal score will then be equal tox + y.To find that subarray of
Gyou can apply Kadane's algorithm that finds the subarray with the maximum sum (in our case overall gain) and runs in O(n) time while only using O(n) space. The general idea is to define two variables,maxendinghereandmaxsofar. The first variable is updated incrementally and for some positioniin your input array (Gin this case) it says what is the maximum sum of a subarray ending in positioni. And the second variable is used to remember the maximum value ofmaxendinghereduring the course of the algorithm. You can find more on the wikipedia page.And a correct solution here.