Code a function in C to get the largest consecutive addition of integer numbers fron an array.

Question

Daniel · Accepted Answer

/* Haven't done C in a while, so pardon me.
 * Essentially, you have to use dynamic
 * programming (see Wikipedia entry on the
 * subject if you are unfamiliar). Create
 * a table where one dimension represents
 * where we start summing ints, and the
 * other dimension represents where we end
 * summing ints. Because not all table
 * entries will be valid, we'll only be
 * filling half of the table.
 */
#define MAX(a,b) ((a) > (b) ? (a) : (b))

int largest_sum(int array[])
{
   /* Create our memoization table */
   int max_sum = INT_MIN, i, row, col;
   int array_size = sizeof(array) / sizeof(int);
   int **mem_table = (int**)malloc(array_size * sizeof(int*));

   for (i = 0; i = column are
    * nonsensical and are ignored.
    */
   for (row = 1; row < array_size; ++row)
   {
      for (col = row; col < array_size; ++col)
      {
         mem_table[row][col] = mem_table[row][col-1] + array[col];
         max_sum = MAX(max_sum, mem_table[row][col]);
      }
   }

   return max_sum;
}

Daniel · Answer

Blech, that's what I get for posting code without testing it first. Sorry about the double-post; wish I could edit my entry.

int largest_sum(int *array, int array_size)
{
   /* Create our memoization table */
   int max_sum = INT_MIN, i, row, col;
   int **mem_table = (int**)malloc(array_size * sizeof(int*));

   for (i = 0; i = column are
    * nonsensical and are ignored.
    */
   for (row = 0; row < array_size - 1; ++row)
   {
      for (col = row + 1; col < array_size; ++col)
      {
         mem_table[row][col] = mem_table[row][col-1] + array[col];
         max_sum = MAX(max_sum, mem_table[row][col]);
      }
   }

   return max_sum;
}

lucita · Answer

best = 0;
current = 0;
for (int i=1 to n)
{
   current = MAX(current + array[i], array[i])
   best = MAX(current, best)
}
return best;

Complexity O(n), additional memory used O(1)

Proof:
MaxSuffixSum(empty) =0
MaxSuffixSum(a[1..n]) = MAX(MaxSuffixSum(a[1..n-1]) + a[n], a[n])

where MaxSuffixSum is a largest sum of numbers from some i to n.

The largest consecutive sum is some suffix, so it is enought to calculate best suffixes ending at all indexes in the array and pick the best one.

Microsoft

Pergunta de entrevista da empresa Microsoft

Respostas da entrevista

Empresas seguidas

Buscas de vagas