# Billboards InterviewStreet - Code Optimization

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;

namespace Billboards
{
class Program
{
static void Main(string[] args)
{
long n, k;
string line;
string[] parts = new string[2];
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++)
{
}
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;
}
}
}

-

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

-
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