# 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.