---
tags: VNOJ, THT, DP, Partial Sum, Prefix Sum, Data Structure, LeThanhMinh, SPyofgame
title: 🌱 Lời giải bài Tin học trẻ 2021 - Vòng khu vực - Bảng B - Dãy Số
author: Editorial-Slayers Team
license: Public domain
---

$\Huge \text{🌱 Lời giải bài Tin học trẻ 2021 - Vòng khu vực - Bảng B - Dãy Số}$

> Nếu bạn cảm thấy Edit này chất lượng tiếc gì một upvote và giới thiệu team với mọi người nhé :heart:
###### 🔗 Link: [https://oj.vnoi.info/problem/tht21_kvb_seq](https://oj.vnoi.info/problem/tht21_kvb_seq)
###### 📌 Tags: `Prefix Sum` ,`Data Structures`
###### 🛠 Work: 6+ hours
###### 👤 Writer:@LeThanhMinh
###### 👥 Editor: @SPyofgame ,@eggdacoder2006
###### 📋 Content:
[TOC]
____
## Ý tưởng :+1:

Với việc tìm dãy con liên tiếp có tổng lớn nhất ta có thể dùng mảng tổng tiền tố:
- Gọi $p[x]$ là tổng các số từ $a[1]$ đến $a[x]$
- Ta có $p[0] = 0$ và $p[x] = p[x - 1] + a[x]$
- Tính chất: $p[r] - p[l - 1] = a_l + a_{l+1} + \dots + a_r$

Tại mỗi vị trí $i$, ta cần tìm tổng lớn nhất có hai số đầu và cuối bằng nhau
$\begin{equation} \begin{split} V_i & = max(a_j + a_{j+1} + \dots + a_i\ |\ a_j = a_i \wedge j < i)\\
& = max(p[i] - p[j - 1]\ |\ a_j = a_i \wedge j < i)\\
& = p[i] - min(p[j - 1]\ |\ a_j = a_i \wedge j < i)
\end{split} \end{equation}$

Tới đây thôi ta có thẻ tính kết quả trong $O(n^2)$có thẻ tính kết quả trong $O(n^2)$

____
## Tối ưu

Đặt $M[x]$ là tổng tiền tố nhỏ nhất xét đến $[i - 1]$ có giá trị $[x]$
- Ta có $V_i = p[i] - M[a[i]]$
- Kết quả bài toán là $res = max(V_i\ |\ 1 \leq i \leq n)$

**Lưu ý:**
- Trường hợp số $x$ xuất hiện lần đầu ta không tính kết quả vì đề yêu cầu $L < R$ hay dãy phải có ít nhất hai phần tử

___
## Nhận xét
* Việc dùng mảng lưu $min$ các tổng tiền tố có phần tử kết thúc là $a_i$ là việc không thể $(|a_i| \le 10^{9})$. **Nhưng** đề bài lại cho $1 \le n \le 10^{5}$ nên thật ra ta chỉ cần một mảng lưu nhiều nhất là $10^{5}$ giá trị. Do đó ta có thể dùng [phương pháp rời rạc hóa](https://vnoi.info/wiki/algo/trick/Roi-rac-hoa-va-ung-dung.md), mảng lúc này chỉ gồm các số nguyên dương từ $1$ đến $10^{5}$ hoặc dùng [hash](https://vnoi.info/wiki/algo/data-structures/hash-table.md).
* Tuy nhiên các cách trên không giúp ta tăng tốc độ code vì vấn đề hằng số nên ta có thể dùng CTDL [map](https://codelearn.io/sharing/cau-truc-du-lieu-than-thanh-mang-ten-map) để thay thế :+1:
____
## Code Minh Hoạ
> **Time:** $O(n \log n)$
> **Space:** $O(n \log n)$
> **Algo:** Prefix sum , Data Structures.
> [color=lightgreen]

:::success
:::spoiler LeMinhThanh code
### Solve

#include<bits/stdc++.h>

#define ll long long

using namespace std;

ll n, a[1000005], pre[1000005];
map<ll, ll> minpre;
map<ll, ll> check;

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        pre[i] = pre[i - 1] + a[i];
    }
    ll res = -1e18;
    minpre[a[1]] = a[1];
    check[a[1]] = true;
    pre[1] = a[1];
    for(int i = 2 ; i <= n; i++)
    {
        if(check[a[i]])
        {
            res = max(res, pre[i] - minpre[a[i]] + a[i]);
            minpre[a[i]] = min(minpre[a[i]], pre[i]);
        }
        else
        {
            minpre[a[i]] = pre[i];
            check[a[i]] =true;
        }
    }
    cout << res;
}

:::
:::success
:::spoiler Spyofgame code

#include <unordered_map>
#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; }
typedef long long ll;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;

int n;
int main()
{
    ios::sync_with_stdio(NULL);
    cin.tie(NULL);

    cin >> n;

    ll s = 0;
    ll res = -LINF;
    unordered_map<int, ll> M;
    for (int i = 1; i <= n; ++i)
    {
        int x;
        cin >> x;    

        if (M.count(x) == false)
        {
            M[x] = s;
        }
        else 
        {
            maximize(res, s - M[x] + x);
            minimize(M[x], s);
        }

        s += x;
    }

    cout << res;
    return 0;
}

:::
:::success

_____
## Bonus

- Bạn có thể giải trong $O(n)$ không ?