Algorithmic problems involving arrays

Find max sum of contiguous sub array

Can be solved in O(n).

Main idea:

  • Track maximum in a variable (e.g. m).
  • Store sequential sum of values in a seperate variable. If sequential sum is smaller than one single value, reset the variable to this value and continue.
  // Example:
  for i..n:
    seqSum = Max(a[i], a[i] + seqSum)
    m = Max(m, seqSum)