CS Academy Array Removal

题目链接：https://csacademy.com/contest/archive/task/array-removal/statement/

题意：给一个元素个数为n的数组，给出一个n的排列，从前到后按照排列的元素从数组中删去一个数，每次删除之前输出数组的最大子数组值。最大子数组值为所有子数组的和的最大值。

思路：由于关心的是子数组的值，而随着操作的执行原数组所有元素都会被删除，因此可以从后往前考虑，并且使用并查集快速获取子数组的和。

从后往前，对于排列中的每个元素，如果当前位置两边有已经恢复过（从前到后删除，从后到前即为恢复）的数据，那么将当前元素作为父亲，两边作为儿子合并，并且更新当前元素值以及临时ans值为父亲+儿子的值。

如果当前位置两边都没回复，则当前位置临时ans值为自己

注意：由于每次都要输出最大值，因此可以用栈保存ans，并且每次确定一个临时ans，取max(ans, stack.top())作为这一次的值。

代码：

 1 const int inf = 0x3f3f3f3f;
 2 const int maxn = 1e5 + 5;
 3 
 4 ll a[maxn];
 5 int n, perm[maxn];
 6 int fa[maxn], vis[maxn];
 7 stack<ll> ans;
 8 
 9 void init(){
10     while(!ans.empty()) ans.pop();
11     memset(a, 0, sizeof(a));
12     memset(perm, 0, sizeof(perm));
13     memset(vis, 0, sizeof(vis));
14     for(int i = 1; i <= n; i++) fa[i] = i;
15 }
16 int find(int x){
17     return (fa[x] == x? fa[x]: find(fa[x]));
18 }
19 ll unite(int x, int y){
20     int fx = find(x), fy = find(y);
21     fa[fy] = fx;
22     return a[fx] = a[fx] + a[fy];
23 }
24 
25 int main(){
26     scanf("%d", &n);
27     init();
28     for(int i = 1; i <= n; i++){
29         scanf("%d", &a[i]);
30     }
31     for(int i = 0; i < n; i++){
32         scanf("%d", &perm[i]);
33     }
34     int i = n / 2, j = n / 2;
35     if(n % 2 == 0) i--;
36     for( i, j; i >= 0 && j < n; i--, j++){
37         swap(perm[i], perm[j]);
38     }
39     for(int i = 0; i < n; i++){
40         int tmp = perm[i];
41         vis[tmp] = 1;
42         if(tmp > 1 && tmp < n && vis[tmp -1] && vis[tmp + 1]){
43             ll tmans = unite(tmp, tmp - 1);
44             tmans = unite(tmp, tmp + 1);
45             if(!ans.empty()) tmans = max(tmans, ans.top());
46             ans.push(tmans);
47         }
48         else if(tmp < n && vis[tmp + 1]){
49             ll tmans = unite(tmp, tmp + 1);
50             if(!ans.empty()) tmans = max(tmans, ans.top());
51             ans.push(tmans);
52         }
53         else if(tmp > 1 && vis[tmp - 1]){
54             ll tmans = unite(tmp, tmp - 1);
55             if(!ans.empty()) tmans = max(tmans, ans.top());
56             ans.push(tmans);
57         }
58         else {
59             ll tmans = 0;
60             if(!ans.empty())  tmans = ans.top();
61             tmans = max(tmans, a[tmp]);
62             ans.push(tmans);
63         }
64     }
65     while(!ans.empty()){
66         ll tmans = ans.top();
67         ans.pop();
68         printf("%lld
", tmans);
69     }
70 }

题目：

Array Removal

Time limit: 1000 ms
Memory limit: 128 MB

Alex has an array of

Alex defines the cost of a subarray as the sum of all the elements in the subarray. Before performing an operation, Alex wants to know the maximum cost of a subarray that doesn't contain any unavailable elements.

Standard input

The first line contains a single integer

The second line contains the

The third line contains a permutation of size

Standard output

The output should contain

Constraints and notes

$10^51≤N≤105$
The values of the array are integers between $10^9109$

Input	Output	Explanation
5 6 1 2 3 2 2 5 1 4 3	14 7 6 5 2	Available elements - Max sum - Max sum subarray:
6 8 3 4 1 5 10 1 4 6 3 2 5	31 23 15 7 5 5