Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Heres the link to the original question . Billboards Link

I initially declared n*k array which led to a Out Of Memory Exception.

Then I resorted to using just 2 * k matrix and alternating between 0 and 1 during each iteration. Now the issue is time limit. As of now 8/10 cases are solved using this approach.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Billboards
{
class Program
{
    static void Main(string[] args)
    {
        long n, k;
        string line;
        string[] parts = new string[2];
        line = Console.ReadLine();
        parts = line.Split(new char[] { ' ' });
        n = long.Parse(parts[0]);
        k = long.Parse(parts[1]);
        long i, j;
        long[]  c = new long[n];
        for (i = 0; i < n; i++)
        {
            c[i] = long.Parse(Console.ReadLine());
        }
        long[][] dp = new long[2][];
        long max = 0;
        int var1, var2, temp;
        var1 = 0;
        var2 = 1;
        for(i=0;i<=1;i++){
            dp[i] = new long[k + 1];
        }

        for (i = 1; i <= n; i++)
        {
            dp[var2][0] = max;
    max = 0;
            for (j = 1; j <= k; j++)
            {
                dp[var2][j] = Math.Max(dp[var1][j - 1] + c[i-1], dp[var1][j]);
        if(dp[var2][j] > max)
        max = dp[var2][j];                     
            }
    temp = var1;
    var1 = var2;
    var2 = temp;
        }            

        max = Max(dp[var1]);              

        Console.WriteLine(max);
    }

    static long Max(long[] arr)
    {
        long max = 0;
        for (long i = 0; i < arr.Length; i++)
        {
            if (arr[i] > max)
            {
                max = arr[i];
            }                
        }
        return max;
    }
}
}
share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

Since we are on a code review forum I would suggest you to give more meaningful names to variables, avoid redundant assignments (e.g. initial array assigned to parts variable is not used), and split the logic into smaller methods that perform distinct functionality. Also you can use Max(IEnumerable<long>) extension method instead of writing your own.

But I guess that's not what you want to hear, so in terms of algorithms I suggest you to apply the A* algorithm to this problem instead of full search. If you find it difficult to understand and implement, I would recommend you to pass the Machine Learning course from Coursera or Introduction to Artificial Intelligence from Udacity

share|improve this answer
    
Thanks for the suggestions. But I am sure there is a DP solution to this problem. Will try that approach too. –  Access Denied Dec 1 '12 at 7:58
    
According to constraints N<=10^5, K<=N. So in worst case you have a nested loop with 10^10 iterations, and that is the reason why your solution timed out. –  almaz Dec 1 '12 at 9:13
    
Yep ..Need to get a better algorithm.. –  Access Denied Dec 1 '12 at 13:13
    
A* explores most promising paths first, so you can find a solution with just slightly more than N iterations –  almaz Dec 1 '12 at 13:44
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.