title: Find Maximum Dot Product Two Arrays Insertion 0S
signature: class Solution {
  
      public Integer findMaximumDotProductTwoArraysInsertion0S(ArrayList<Integer> a, ArrayList<Integer> b, Integer m, Integer n) {
test_code: import static java.util.Map.entry;  
  import java.util.*;
  import java.lang.*;
  // TESTING CODE 
  // ============================================
  class QuestionEvaluator {
      public static String validateSolution(ArrayList<Integer> a, ArrayList<Integer> b, Integer m, Integer n, Integer expected){
          try{
              Driver driver = new Driver();
              if (driver.run(a, b, m, n,expected)){
                  return "PASSED";
              }
              return "FAILED";
              
          } catch (Exception exception_obj){
              return exception_obj.getClass().getSimpleName();
          }
  
      }
      public static void main(String[] args) {
          String result;
          result = validateSolution(new ArrayList<>(Arrays.asList(7, 9, 22, 68)), new ArrayList<>(Arrays.asList(14, 22, 54, 58)), 3, 2, 610);
          System.out.println(String.format("%s%s","TEST-0...",result));    
      
          result = validateSolution(new ArrayList<>(Arrays.asList(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)), new ArrayList<>(Arrays.asList(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);
          System.out.println(String.format("%s%s","TEST-1...",result));    
      
          result = validateSolution(new ArrayList<>(Arrays.asList(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)), new ArrayList<>(Arrays.asList(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);
          System.out.println(String.format("%s%s","TEST-2...",result));    
      
          result = validateSolution(new ArrayList<>(Arrays.asList(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)), new ArrayList<>(Arrays.asList(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);
          System.out.println(String.format("%s%s","TEST-3...",result));    
      
          result = validateSolution(new ArrayList<>(Arrays.asList(-94, -76, -68, -50, -28, -20, 18, 24, 30, 54, 74, 84, 98)), new ArrayList<>(Arrays.asList(-88, -80, -78, -68, -44, -38, 42, 50, 62, 68, 70, 80, 92)), 11, 8, 31016);
          System.out.println(String.format("%s%s","TEST-4...",result));    
      
          result = validateSolution(new ArrayList<>(Arrays.asList(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)), new ArrayList<>(Arrays.asList(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);
          System.out.println(String.format("%s%s","TEST-5...",result));    
      
          result = validateSolution(new ArrayList<>(Arrays.asList(14, 27, 43, 49)), new ArrayList<>(Arrays.asList(51, 59, 76, 83)), 2, 2, 2307);
          System.out.println(String.format("%s%s","TEST-6...",result));    
      
          result = validateSolution(new ArrayList<>(Arrays.asList(78, -26, -12, 38, -90)), new ArrayList<>(Arrays.asList(14, 50, -6, -38, 80)), 3, 2, 492);
          System.out.println(String.format("%s%s","TEST-7...",result));    
      
          result = validateSolution(new ArrayList<>(Arrays.asList(0, 1, 1, 1)), new ArrayList<>(Arrays.asList(0, 0, 0, 1)), 3, 2, 0);
          System.out.println(String.format("%s%s","TEST-8...",result));    
      
          result = validateSolution(new ArrayList<>(Arrays.asList(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)), new ArrayList<>(Arrays.asList(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);
          System.out.println(String.format("%s%s","TEST-9...",result));    
      
      }
  }
  
  class Driver{
      public boolean run(ArrayList<Integer> a, ArrayList<Integer> b, Integer m, Integer n, Integer expected){
  
          PLACEHOLDER_CLS_NAME sol = new PLACEHOLDER_CLS_NAME();
          return validateSolution(sol.PLACEHOLDER_FN_NAME(a, b, m, n),expected);
      }
      
      public boolean validateSolution(Integer actual, Integer expected){
          return actual.equals(expected);
      }
  }
  
  
  // SOLUTION CODE
  // ============================================
  PLACEHOLDER_CODE_BODY
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 ];
  }