我的算法书 -

配对最值

$A = \{a_1,a_2,\cdots, a_n\}$

A' = \{ a_i + y \mid a_i \in A \}

则 $\max(A') = \max(A) + y$

子集最值

如果: $A = B \cup C$

\max(A \cup B) = \max(\max(A) , \max(B))

\min(A \cup B) = \min(\min(A) , \min(B))

最大二值和

问题: 求集合 $A$ 中两个元素的和的最大值

解法一: 找出集合的最大值和次最大值, 然后相加

cpp

copy

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

        int n;
int a[maxn];

int max1 = -inf,max2=-inf;
void upd_max_2(int t) {
    if( t > max1 ) {
        max2 = max1;
        max1 = t;
    } else if( t > max2 ) {
        max2 = t;
    }
}

for(int i =1;i<=n;i++) {
    upd_max_2(a[i]);
}

cout << max1 + max2 << endl;

解法二:

Open in Excalidraw

$A = \{ a_1,a_2 ,\cdots , a_n \}$
$A' = \{ (a_j,a_i) \mid i < j, a_j \in A ,a_i \in A \}$ 集合 : 表示任意两个元素的有序配对组成的元组集合
$B_i = \{ (a_j,a_i) \mid j < i , a_j \in A ,a_i \in A \}$ 集合 : 它表示第i个元素 $a_i$ 和前面的所有元素 $a_j$ ( $j<i$ ), 组成的二元元组组成的集合.

$\max(A')$ 表示集合中元组的两个值的和的最大值

A' = \bigcup_{i=1}^n B_i

于是得到

\max (A') = \max_{i=1}^n( \max(B_i))

设: $f(i) = \max(a_1,a_2 , \cdots ,a_i)$

\begin{aligned} \max(B_i) &= \max(a_1,a_2,\cdots,a_{i-1} ) + a_i \\ &= f(i-1) + a_i \end{aligned}

容易想到 $f(i) = \max(f(i-1),a_i)$

如果我们用代码表示上面的计算过程,那么得到一个 $O(n)$ 的代码如如下:

cpp

copy

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

        int a[maxn]; // 原始数据
int B[maxn]; // B[i] 表示以 a_i 和 前面的某个数a_j的最大和
int f = a[1]; // f 表示前面的某个数a_j的最大值
int ans;

template<typename T>
void upd(T& a, T b) { if( a < b ) a = b; }


for(int i =2;i<=n;i++) {
    B[i] = f + a[i];
    // 核心 两行代码
    upd(ans,f + a[i]); // 更新答案, 得到 a[i] 为结尾的分类的最大值
    upd(f,a[i]); // 更新 f, 为后面的 B[i] 服务
}

总结,用到的思想

集合最值与子集最值的关系
组合数学,集合不重不漏的分类
滑动窗口

目录

配对最值

子集最值

最大二值和