# 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' ,'Rời rạc hóa' ,'Hash'.
###### 🛠 Work: At least 14 hours
###### 👤 Writter:@LeThanhMinh
###### 👥 Contributor: [@Editorial-Slayers Team](https://hackmd.io/@Editorial-Slayers)
###### 📋 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 $prefix$ cộng dồn bằng việc khi xét tới $i$ ta có tổng từ $1$ đến $i$ là $prefix[i]$ việc tìm dãy con liên tiêp có tổng lớn nhất từ $1$ đến $i$ chỉ đơn giản là $max(prefix[i] - min(prefix[j]))$ $(1<=j<i<=n)$
* Vậy còn điều kiện $a[i]$ và $a[j]$ bằng nhau thì sao ?
* Ta có thể dùng một mảng $minprefix[k]$ lưu $min$ của các tổng tiền tố $prefix[i]$ có giá trị $a[i] = k$.
--> vậy ta với mỗi $prefix[i]$ ta có thể tìm dãy con liên tiếp có tổng lớn nhất bằng cách trừ đi cho $minprefix[a[i]]$ thỏa mãn với điều kiện đề bài nhưng trước đó phải có một giá trị bằng với $a[i]$ đảm bảo có phần tử đầu bằng với $a[i]$.
___
## Nhận xét
* Việc dùng mảng lưu $min$ của tổng tiền tố có phần tử cuối cùng là $a[i]$ là việc không thể ,vì $|a[i]|<=10^{9}$ nên mảng phải có chỉ số âm hoặc có độ dài $10^{9}$ là điều không thể .**Nhưng** đề bài lại cho $1<= n <= 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ị .Về việc này bạn 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) sort lại dùng struct (c++) vừa lưu giá trị hiện tại vừa lưu vị trí ta có các số sau khi rời rạc đi chỉ có dạng là 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) việc dùng như vậy là quá cồng kềnh nên ta có thể dùng cấu trúc dữ liệu [map](https://codelearn.io/sharing/cau-truc-du-lieu-than-thanh-mang-ten-map) để thay thế :+1:
____
## Code Hướng dẫn
>[color=red] Đừng copy-paste từ lời giải này lời giải này chỉ mang tính chất tham khảo . **Nên nhớ lời nói này là tốt cho bản thân của bạn**
:::success
:::spoiler code
### Solve

   const long long INF = 1e18 +7;
   const long long MAXN = 1e6 +7; // nên lưu như vậy tránh trường hợp tràn mảng
   map<long long , long long > minprefix;
   map<long long , bool> check;
   long long prefix[MAXN] , a[MAXN];
   int main(){
    for(int i = 1; i<=n ; i++){
        cin>>a[i] ;
    }
    minprefix[a[1]] = a[1];
    check[a[1]] =true;
    prefix[1] = a[1];
    for(int i = 2 ; i <= n ; i++){
        prefix[i] = prefix[i-1] + a[i]; // tính tổng các dãy con liên tiếp từ 1 đến i 
        // kiểm tra xem đã có L = a[i] hay không
        if(check[a[i]] == true){
              res = max(res,prefix[i] - minprefix[a[i]] + a[i]); // thao tác cập nhật kết quả
              minprefix[a[i]] = (minprefix[a[i]] , prefix[i]);// cập nhật giá trị bé nhất 
        } 
        //  nếu không có một L = a[i] nào thì ta bắt đầu khởi gán
        if(check[a[i]] == false){
              minprefix[a[i]] = prefix[i];
              check[a[i]] =true;// xác nhận đã có một L thỏa mãn L= a[i]
        }
    }
    cout<<res;
  }