- array-rearrange, Arrays, Greedy, Mathematical, Pattern Searching, subarray

Minimize sum of product of same-indexed elements of two arrays by reversing a subarray of one of the two arrays

  import java.io.*;import java.util.*;  public class Main {                  static void minimumProdArray(long a[],                                 long b[], int l)    {        long total = 0;                  for (int i = 0; i < a.length; ++i) {            total += a[i] * b[i];        }          long min = Integer.MAX_VALUE;          int first = 0;        int second = 0;                  for (int i = 0; i < a.length; ++i) {              int left = i - 1;            int right = i + 1;            long total1 = total;            while (left >= 0 && right < a.length) {                                  total1 -= a[left] * b[left]                          + a[right] * b[right];                                  total1 += a[left] * b[right]                          + a[right] * b[left];                                                  if (min >= total1) {                      min = total1;                    first = left;                    second = right;                }                  –left;                ++right;            }        }                  for (int i = 0; i < a.length; ++i) {              int left = i;            int right = i + 1;            long total1 = total;              while (left >= 0 && right < a.length) {                                  total1 -= a[left] * b[left]                          + a[right] * b[right];                                  total1 += a[left] * b[right]                          + a[right] * b[left];                                                  if (min >= total1) {                    min = total1;                    first = left;                    second = right;                }                                  –left;                ++right;            }        }                  if (min < total) {              reverse(first, second, a);                          print(a, b);        }          else {            print(a, b);        }    }          static void reverse(int left, int right,                        long arr[])    {        while (left < right) {            long temp = arr[left];            arr[left] = arr[right];            arr[right] = temp;            ++left;            --right;        }    }          static void print(long a[], long b[])    {        int minProd = 0;          for (int i = 0; i < a.length; ++i) {            System.out.print(a[i] + " ");        }        System.out.println();        for (int i = 0; i < b.length; ++i) {            System.out.print(b[i] + " ");            minProd += a[i] * b[i];        }        System.out.println();        System.out.println(minProd);    }          public static void main(String[] args)    {        int n = 4;        long a[] = { 2, 3, 1, 5 };        long b[] = { 8, 2, 4, 3 };          minimumProdArray(a, b, n);    }}