credzba - check out this gist code snippet

Here's the code snippet!

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

Sliding Window Algorithm

The sliding window algorithm is used for finding a pattern with the smallest window size. It is adaptable and moves along until you have found the smallest window size.

It is actually very optimal and done in O(N) time. It has a max scan of 2N operations, and initially it creates a window that fits the pattern. Once found, it amortizes the cost at O(1) for increasing the window size to span the entire list.

So in order to accomplish this, we will need to have two map-type structures. has[] and need[] maps will be used to verify if we have the accurate number of times a character needs to apply to the pattern.

Let's continue with the code:

int has[256] = {0,};
int need[256] = {0,};

int min_window(string text, string pattern) {
   for (int i = 0; i < pattern.size; ++i)
      ++need[pattern[i]];

   int matchedLen = 0;
   int minWindow = text.size() + 1;
   for (int i = 0, j = 0; i < text.size(); ++i) {
      if (need[text[i]] == 0) continue;

      ++has[text[i]];

      if (need[text[i]] >= has[text[i]])
          ++matchedLen;

      if (matchedLen == pattern.size()) {
         while (need[text[j]] == 0 || 
                has[text[j]] > need[text[j]]) {

            if (has[text[j]] > need[text[j]])
                --has[text[j]];

            ++j;
         }
         // Update window size.
         minWindow = std::min(minWindow, i - j + 1);
      }
   }
   return minWindow;
}