title: Find Maximum Dot Product Two Arrays Insertion 0S
signature: pub fn find_maximum_dot_product_two_arrays_insertion_0s(a: Vec<i32>, b: Vec<i32>, m: i32, n: i32) -> i32 {
test_code: use std::collections::HashMap;
  use std::collections::HashSet;
  use std::cmp::*;
  use std::collections::*;
  use std::fmt::*; 
  
  
  // SOLUTION CODE
  // ============================================
  PLACEHOLDER_CODE_BODY
  
  // TESTING CODE 
  // ============================================
  pub fn validate_solution(actual: i32, expected: i32)->bool{
  return actual==expected
  }
  pub fn driver(a: Vec<i32>, b: Vec<i32>, m: i32, n: i32, expected: i32)->String{
      if validate_solution(PLACEHOLDER_FN_NAME(a, b, m, n), expected) {
        return "PASSED".to_string();
      };
      return "FAILED".to_string();
  
  }
  
  fn main() {
      println!("TEST-0...{}", driver(
        Vec::from([7, 9, 22, 68]), Vec::from([14, 22, 54, 58]), 3, 2, 
        610
      ));
      
      println!("TEST-1...{}", driver(
        Vec::from([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]), Vec::from([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
      ));
      
      println!("TEST-2...{}", driver(
        Vec::from([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]), Vec::from([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
      ));
      
      println!("TEST-3...{}", driver(
        Vec::from([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]), Vec::from([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
      ));
      
      println!("TEST-4...{}", driver(
        Vec::from([-94, -76, -68, -50, -28, -20, 18, 24, 30, 54, 74, 84, 98]), Vec::from([-88, -80, -78, -68, -44, -38, 42, 50, 62, 68, 70, 80, 92]), 11, 8, 
        31016
      ));
      
      println!("TEST-5...{}", driver(
        Vec::from([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]), Vec::from([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
      ));
      
      println!("TEST-6...{}", driver(
        Vec::from([14, 27, 43, 49]), Vec::from([51, 59, 76, 83]), 2, 2, 
        2307
      ));
      
      println!("TEST-7...{}", driver(
        Vec::from([78, -26, -12, 38, -90]), Vec::from([14, 50, -6, -38, 80]), 3, 2, 
        492
      ));
      
      println!("TEST-8...{}", driver(
        Vec::from([0, 1, 1, 1]), Vec::from([0, 0, 0, 1]), 3, 2, 
        0
      ));
      
      println!("TEST-9...{}", driver(
        Vec::from([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]), Vec::from([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
      ));
      
  }
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 ];
  }