Largest Subarray Sum

The largest subarray sum solution is based off of dp, and is based off previous values. Dynamic Programming (DP) is an iteratively solution based off of maximal substructure properties, where you can solve a bigger solution based off of smaller problems.

For this solution, there's a running counter for the max sum that we have hit thus far. If the value ever goes negative, we will reset the current max to the value (or 0, if there is at least one positive number).

By doing this - it allows us to go through the largest sum arrays by just iterating over the elements.

Let's go and see the code.

int largest_sum(vector A) {
   int maxSoFar = A[0], maxEndingHere = A[0];
   for (int i = 1; i < A.size(); ++i) {
      if (maxEndingHere < 0)
         maxEndingHere = A[i];
      else
         maxEndingHere += A[i];

      maxSoFar = std::max(maxSoFar, maxEndingHere);
   }
   return maxSoFar;
}