title: Find Maximum Dot Product Two Arrays Insertion 0S
signature: int findMaximumDotProductTwoArraysInsertion0S(vector<int> a, vector<int> b, int m, int n) {
test_code: #include <algorithm>
  #include <assert.h>
  #include <cstdlib>
  #include <iostream>
  #include <map>
  #include <set>
  #include <string>
  #include <tuple> 
  #include <unordered_map>
  #include <vector>
  #include <math.h>
  #include <cmath>
  #include <bits/stdc++.h>
  #include <numeric>
  #include <functional>
  
  using namespace std;
  
  // SOLUTION CODE
  // ============================================
  PLACEHOLDER_CODE_BODY
  
  // TESTING CODE 
  // ============================================
  bool validateSolution(int actual, int expected){
      return actual == expected;
  }
  
  string driver(vector<int> a, vector<int> b, int m, int n, int expected){
      try
      {
          if (validateSolution(PLACEHOLDER_FN_NAME(a, b, m, n), expected)){
              return "PASSED";
          }
          return "FAILED";
      }
      catch (const std::overflow_error& exception_obj)
      {
          return typeid(exception_obj).name();
      }
      catch (const std::runtime_error& exception_obj)
      {
          return typeid(exception_obj).name();
      }
      catch (const std::exception& exception_obj)
      {
          return typeid(exception_obj).name();
      }
      catch (...)
      {
          return "UNK_ERROR";
      }
  }
  
  int main() {
      string result = "";
  
      result = driver({7, 9, 22, 68}, {14, 22, 54, 58}, 3, 2, 610); 
      cout << "TEST-" << 0 << "..."
           <<  result
           << "\n";
  
      result = driver({24, 40, 98, 58, -24, 24, 76, 48, -92, -16, -46, -48, -70, 88, 66, 2, 44, 36, 34, 34, 46, 90, -80, -24, -58, 68, 72, -20, -62, -40}, {30, -88, 6, -26, -76, 14, -80, -30, -58, 76, 40, -28, -54, 38, -60, -60, 88, -80, -22, 90, 50, -48, 68, -26, 26, -2, 68, -16, 88, -72}, 22, 22, 7952); 
      cout << "TEST-" << 1 << "..."
           <<  result
           << "\n";
  
      result = driver({0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, 22, 19, 0); 
      cout << "TEST-" << 2 << "..."
           <<  result
           << "\n";
  
      result = driver({32, 15, 41, 41, 4, 42, 22, 33, 33, 11, 68, 5, 41, 80, 39, 15, 36, 75, 41, 11, 25, 40, 50, 19, 39, 12, 75, 28, 52, 20, 63, 5, 27, 53, 19, 62, 98, 72, 10, 90, 74, 93, 52, 81, 91, 65, 90, 93}, {80, 18, 9, 29, 62, 89, 4, 40, 47, 15, 35, 82, 22, 97, 63, 54, 7, 58, 64, 73, 54, 79, 21, 21, 20, 19, 56, 42, 6, 97, 7, 34, 55, 35, 57, 86, 73, 88, 20, 29, 48, 52, 8, 77, 2, 12, 6, 47}, 30, 25, 50904); 
      cout << "TEST-" << 3 << "..."
           <<  result
           << "\n";
  
      result = driver({-94, -76, -68, -50, -28, -20, 18, 24, 30, 54, 74, 84, 98}, {-88, -80, -78, -68, -44, -38, 42, 50, 62, 68, 70, 80, 92}, 11, 8, 31016); 
      cout << "TEST-" << 4 << "..."
           <<  result
           << "\n";
  
      result = driver({1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0}, {1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1}, 21, 33, 0); 
      cout << "TEST-" << 5 << "..."
           <<  result
           << "\n";
  
      result = driver({14, 27, 43, 49}, {51, 59, 76, 83}, 2, 2, 2307); 
      cout << "TEST-" << 6 << "..."
           <<  result
           << "\n";
  
      result = driver({78, -26, -12, 38, -90}, {14, 50, -6, -38, 80}, 3, 2, 492); 
      cout << "TEST-" << 7 << "..."
           <<  result
           << "\n";
  
      result = driver({0, 1, 1, 1}, {0, 0, 0, 1}, 3, 2, 0); 
      cout << "TEST-" << 8 << "..."
           <<  result
           << "\n";
  
      result = driver({12, 69, 57, 7, 52, 14, 15, 83, 67, 57, 15, 86, 81, 43, 1, 64, 45, 68, 30, 23, 14, 70, 13, 51, 23, 33, 98, 68, 24, 43, 12, 82, 46}, {12, 48, 57, 40, 47, 36, 22, 50, 68, 98, 77, 78, 39, 55, 87, 75, 65, 27, 33, 27, 70, 34, 67, 71, 84, 33, 7, 61, 3, 9, 67, 92, 60}, 17, 32, 0); 
      cout << "TEST-" << 9 << "..."
           <<  result
           << "\n";
  
      return 0;
  }
source_py: def find_maximum_dot_product_two_arrays_insertion_0s(A, B, m, n):
      dp = [[0 for i in range((m + 1))] for j in range((n + 1))]
      for i in range(1, (n + 1), 1):
          for j in range(i, (m + 1), 1):
              dp[i][j] = max((dp[(i - 1)][(j - 1)] + (A[(j - 1)] * B[(i - 1)])), dp[i][(j - 1)])
      return dp[n][m]
source_cpp: long long int find_maximum_dot_product_two_arrays_insertion_0s(vector<int> A, vector<int> B, int m, int n) {
    long long int dp [ n + 1 ] [ m + 1 ];
    memset ( dp, 0, sizeof ( dp ) );
    for ( int i = 1;
    i <= n;
    i ++ ) for ( int j = i;
    j <= m;
    j ++ ) dp [ i ] [ j ] = max ( ( dp [ i - 1 ] [ j - 1 ] + ( A [ j - 1 ] * B [ i - 1 ] ) ), dp [ i ] [ j - 1 ] );
    return dp [ n ] [ m ];
  }