---
tags: Private, LQDOJ, Practice VNOI, DP, Space Optimized, SPyofgame, kazamahoang
title: 🔒 Tích chập (Contest Practice VNOI 2021 Round 1)
author: Editorial-Slayers Team
license: Free to use in private but unless required by problem author, contest consent, applicable law or agreed to in writing, editorial distributed under the license is distributed on an “AS IS” BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. Under this license, Editorial-Slayers Team WILL NOT TAKE IN CHARGE FOR the editorial to be published publicly by the third party using this editorial.
---

<style>
.markdown-body { max-width: 2048px; }
</style>

$\Huge \text{🔒 Tích chập (Contest Practice VNOI 2021 Round 1)}$

-----

###### 🔗 Link: [https://lqdoj.edu.vn/problem/d13r1convol](https://lqdoj.edu.vn/problem/d13r1convol)
###### 📌 Tags: `DP`, `Space Optimized`
###### 👤 Writter: @SPyofgame
###### 👥 Contributor: [@kazamahoang](https://codeforces.com/profile/https://codeforces.com/profile/PhaiCoGiaiQuocGia)
###### 📋 Content:

[TOC]

-----
## Hướng dẫn

Ta gọi $f[i][j]$ là tổng lớn nhất tính đến số thứ $i$ tong dãy $a[]$ và số thứ $j$ trong dãy $b[]$

Ta có 2 lựa chọn:
- Chọn tiếp tích $a[i] \times b[j]$ vào dãy có tổng lớn nhất khi mới xét đến $a[i - 1]$ và $b[j - 1]$
- Tạo tích mới xuất hiện từ bây giờ, bỏ qua tổng của dãy lớn nhất trước đó

Trong hai cách chọn ở trên, ta chọn tổng lớn hơn nên:
- $f[i][j] = max(f[i - 1][j - 1] + a[i] \times b[j], a[i] \times b[j])$

Để cho tiện tính toán, ta định nghĩa:
$\begin{cases}
f[i][0] = 0 & \forall i \geq 0\\
f[0][j] = 0 & \forall j \geq 0\\
\end{cases}$

Kết quả bài toán là $max(f[i][j])$

**Lưu ý**:
- Vì dãy được chọn phải không rỗng nên kết quả có thể âm
- Để tiện cài đặt thì ban đầu khơi tạo $max = -\infty$

### Code

> **Time:** $O(n \times m)$
> **Space:** $O(n \times m)$
> **Algo:** DP
> [color=lightgreen]

:::success
:::spoiler Code

#include <iostream>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

const int LIM = 5e3 + 53;

int n;
int a[LIM];
int b[LIM];
long long f[LIM][LIM];
int main()
{
    ios::sync_with_stdio(NULL);
    cin.tie(NULL);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) cin >> b[i];

    long long res = -1e18;
    for (int i = 0; i <= n; ++i) f[0][i] = 0;
    for (int i = 1; i <= n; ++i)
    {
        f[i][0] = 0;
        for (int j = 1; j <= n; ++j)
        {
            long long v = (1LL * a[i] * b[j]);
            f[i][j] = max(f[i - 1][j - 1] + v, v);
            maximize(res, f[i][j]);
        }
    }

    cout << res;
    return 0;
}

:::

-----
## Tối ưu không gian

Nhận thấy ta duyệt qua lần lượt các hàng, ta có thể tính $f[i][j]$ dựa trên $f[i - 1][j]$. Khi này các $f[p][q]$ với $p < i - 1$ trở đi không cần xét đến nữa, nên ta có thể in đè kết quả của $f[i][j]$ lên $f[i][j - 2]$

### Code

> **Time:** $O(n \times m)$
> **Space:** $O(n + m)$
> **Algo:** DP, Space Optimized
> [color=lightgreen]

:::success
:::spoiler Code

#include <iostream>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

const int LIM = 5e3 + 53;

int n;
int a[LIM];
int b[LIM];
long long f[2][LIM];
int main()
{
    ios::sync_with_stdio(NULL);
    cin.tie(NULL);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) cin >> b[i];

    long long res = -1e18;
    for (int i = 0; i <= n; ++i) f[0][i] = 0;
    for (int i = 1; i <= n; ++i)
    {
        bool cur = i & 1;
        bool pre = !cur;

        f[cur][0] = 0;
        for (int j = 1; j <= n; ++j)
        {
            long long v = (1LL * a[i] * b[j]);
            f[cur][j] = max(f[pre][j - 1] + v, v);
            maximize(res, f[cur][j]);
        }
    }

    cout << res;
    return 0;
}

:::

-----
## Bonus

Nhận thấy ta duyệt qua lần lượt các hàng rồi qua lần lượt các cột, ta có thể tính $f[i][j]$ dựa trên $f[i - 1][j - 1]$. Khi này (các $f[p][q]$ với $p < i - 1$) và ($f[p][q]$ với $p \leq i$ và $q < j$) trở đi không cần xét đến nữa, nên ta có thể in đè kết quả của $f[i][j]$ lên chính bản thân nó $f[i][j]$

Nói một cách khác ta có thể tái định nghĩa $g[j]$ là max kết quả tìm được xét tới tổng $j$ khi xét lần lượt các hàng và lần lượt các cột

### Code

> **Time:** $O(n \times m)$
> **Space:** $O(n + m)$
> **Algo:** DP, Space Optimized
> [color=lightgreen]

:::success
:::spoiler Code

/// @Author:       SPyofgame
/// @Contributor:  kazamahoang
/// @License:      Free to use
/// @Problem:      Find Max(a[p] * b[q] + a[p + 1] * b[q + 1] + ..)
/// @Submit:       https://lqdoj.edu.vn/problem/d13r1convol
///
/// @Algorithm:    Prefixmax DP O(n^2) time
/// @Optimization: Space Optimized O(n) space
/// @Editorial:
///     f[i][j] = maximum value calculated up to row [i] column [j]
///     f[0][j] = 0
//      f[i][0] = 0
///     f[i][j] = max(f[i-1][j-1] + a[i] * b[j], a[i] * b[j])
///     result  = max(f[i][j])
 
#include <iostream>
 
using namespace std;
 
template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }
 
const int LIM = 5e3 + 53;
 
int n;
int a[LIM];
int b[LIM];
long long f[LIM];
int main()
{
    ios::sync_with_stdio(NULL);
    cin.tie(NULL);
 
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) cin >> b[i];
 
    long long res = -1e18;
    for (int i = 0; i <= n; ++i) f[i] = 0;
    for (int i = 1; i <= n; ++i)
    {
        bool cur = i & 1;
        bool pre = !cur;
 
        f[0] = 0;
        for (int j = n; j >= 1; --j)
        {
            long long v = (1LL * a[i] * b[j]);
            f[j] = max(f[j - 1] + v, v);
            maximize(res, f[j]);
        }
    }
 
    cout << res;
    return 0;
}