Billboards InterviewStreet - Code Optimization

Question

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;
    }
}
}

Answer 1

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