HackerRank Walmart codesprint algorithm - fibonacci sum - submission 1 - score 0, out-of-memory, array size is 4000MB; memory should be <=512MB.

FibonacciSum_sub1.cs

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

namespace InterestingFibonacciSum
{
    class InterestingFibonacciSum_OutofMemory
    {
        /*
         * https://www.hackerrank.com/contests/walmart-codesprint-algo/challenges/fibonacci-sum-1
         * Oct. 29, 2016
         * Spent two hours to read problem statement
         * 11:30am - 1:30am
         * 
         * 7:12pm - start to write some code
         * Figure out things in detail
         * 
         * 9:12pm complete the coding
         * 9:12pm put into HackerRank to test the code 
         * 
         */
        static void Main(string[] args)
        {
            //testing2(); 
            process();
        }

        private static void testing1()
        {
            int n = 2;
            int[] arr = { 1, 1 };

           // int result = calculate(n, arr);
        }

        private static void testing2()
        {
            int n = 3;
            int[] arr = { 1, 2, 3 };

          //  int result = calculate(n, arr);
        }

        /*
         * 9:33pm 
         * first, test the function is working 
         * ignore out-of-memory issue 
         */
        private static void process()
        {
            int q = Convert.ToInt32(Console.ReadLine());
            int SIZE = 100000;           // 10^5 

            int[] chosen = new int[SIZE];

            int start = 0; 
            for (int i = 0; i < q; i++)
            {
                int n = Convert.ToInt32(Console.ReadLine());   // 10^5 upper limit, size of array
                int[] arr = new int[n];

                arr = cToInt(Console.ReadLine().Split(' '));

                Console.WriteLine(calculate(n, arr, chosen, ref start));
            }
        }

        /*
         * start: 7:15pm 
         * end: 7:19pm
         */
        private static int[] cToInt(string[] arr)
        {
            if (arr == null || arr.Length == 0)
                return new int[0];

            int n = arr.Length;
            int[] res = new int[n];

            for (int i = 0; i < n; i++)
            {
                res[i] = Convert.ToInt32(arr[i]);
            }

            return res;
        }       

        private static int calculate(int n, int[] arr, int[] chosen, ref int start)
        {
            int count = 0;

            int[] sum1 = sumC(n, arr);

            int index = 0;
            for (int i = 0; i < n; i++)
                for (int j = i; j < n; j++)
                {
                    int L = i;
                    int R = j;

                    int AL2R = (L == R) ? arr[L] : (sum1[R] - sum1[L] + arr[L]);

                    chosen[start + index] = AL2R;
                    index++; 
                }

            int[] newArr = new int[index];
            Array.Copy(chosen, start, newArr, 0, index);

            Array.Sort(newArr);

            start = start + index; 
            return count = fiboSmart(newArr);
        }

       
        /*
         * 8:25pm 
         * To reduce the variation of calculation from O(n^2) to O(n)
         * sum(A) = sumC[R] - sumC[L]
         * 
         * 8:40pm 
         * L, R two variable, each is O(n), so LR pair will be O(n^2)
         * but, we use sumC to get the difference based on O(n) size array
         * 
         * 8:55pm 
         * cut the size to 10^9 + 7
         * module calculation 
         */
        private static int[] sumC(int n, int[] arr)
        {
            int[] sum = new int[n];
            int module = 1000000000 + 7;

            sum[0] = arr[0];
            for (int i = 1; i < n; i++)
            {
                sum[i] = (sum[i - 1] + arr[i]) % module;
            }

            return sum;
        }                      

        /*
         * 10:28pm 
         * start to work on the function
         * 
         * 10:39pm 
         * came out an idea, and then implemented the code
         */
        private static int fiboSmart(int[] chosen)
        {             
            int SIZE = 1000000000 + 7;
            int module = SIZE;             

            int len = chosen.Length;
            int index = 0; 

            int tmp0 = 0;
            while (index < len && chosen[index] == 0)
            {                 
                index++;                 
            }

            int count = 0; 
            int tmp1  = 1;

            while (index < len && chosen[index] == 1)
            {                 
                count = (count + 1) % module;
                index++;               
            }

            int sum = 0;
            for (int i = 2; i <= chosen[len-1]; i++)
            {
                sum = (tmp0 + tmp1) % SIZE;

                while (index < len && chosen[index] == i)
                {                    
                    count = (count + sum) % module;
                    index++;                                      
                }

                tmp0 = tmp1;
                tmp1 = sum;
            }

            return count;            
        }
    }
}