分治进阶：跨越中点，以及只走一边

// 最大子段和 —— 暴力：枚举所有的段
//
// 输入：第一行 n，第二行 n 个整数（可能有负数）
// 输出：所有**非空连续子段**里，和最大的那个是多少
//
// 例：-2 1 -3 4 -1 2 1 -5 4  →  答案 6（子段 4 -1 2 1）
//
// 注意「非空」：即使全是负数，也必须选至少一个，
// 所以那时答案是「最大的那个负数」，不是 0。这是最容易写错的边界。
//
// 暴力：枚举左端点，往右一路累加，边加边更新答案。O(n²)。
// （这里用了第 5 章那一招 —— 不要另开一重循环去求段和，边枚举边累加就行。）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    if (n <= 0) { cout << 0 << "\n"; return 0; }

    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    long long best = a[0];
    for (int l = 0; l < n; l++) {
        long long sum = 0;
        for (int r = l; r < n; r++) {
            sum += a[r];
            best = max(best, sum);
        }
    }

    cout << best << "\n";
    return 0;
}

// 最大子段和 —— 分治
//
// 输入输出和 maxsubBrute.cpp 完全一样。
//
// 分治三步（第 11 章那个框架，一模一样）：
//
//   最大子段  =  三者取最大：
//       ① 完全落在左半边的     → 递归解决
//       ② 完全落在右半边的     → 递归解决
//       ③ **跨过中点的**       → 这才是要动脑的部分
//
// 跨过中点的那一段长什么样？它必然是
//     「左半边里以 mid 结尾的某一段」 + 「右半边里以 mid+1 开头的某一段」。
//
// 这两截可以各自 O(长度) 地扫出来：
//     从 mid 往左走，一路累加，记住最大值 → 左边最好的后缀
//     从 mid+1 往右走，一路累加，记住最大值 → 右边最好的前缀
// 两个加起来就是跨越中点的最优解。
//
// ⚠ 这两截都**必须非空**（至少含 mid 和 mid+1 各一个元素），
//   否则「跨过中点」这个前提就不成立了，会和 ①② 重复。
//
// 复杂度：T(n) = 2T(n/2) + O(n) —— 和归并排序一模一样，所以是 O(n log n)。

#include <bits/stdc++.h>
using namespace std;

vector<long long> a;

long long solve(int l, int r) {
    if (l == r) return a[l];                    // 边界：只剩一个元素

    int mid = l + (r - l) / 2;
    long long best = max(solve(l, mid), solve(mid + 1, r));    // ①②

    // ③ 跨过中点：左边最好的后缀 + 右边最好的前缀
    long long sum = 0, leftBest = LLONG_MIN;
    for (int i = mid; i >= l; i--) { sum += a[i]; leftBest = max(leftBest, sum); }

    sum = 0;
    long long rightBest = LLONG_MIN;
    for (int i = mid + 1; i <= r; i++) { sum += a[i]; rightBest = max(rightBest, sum); }

    return max(best, leftBest + rightBest);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    if (n <= 0) { cout << 0 << "\n"; return 0; }

    a.assign(n, 0);
    for (int i = 0; i < n; i++) cin >> a[i];

    cout << solve(0, n - 1) << "\n";
    return 0;
}

// 最大子段和 —— 从左到右扫一遍就够了（O(n)）
//
// 输入输出和前两份完全一样，但只有三行核心代码。
//
// 想法：**以第 i 个元素结尾**的最大子段和是多少？记作 cur。
//   要么接着前面那一段往下延（cur + a[i]），
//   要么干脆从 a[i] 自己重新开始（a[i]）—— 取大的那个。
//
//     cur = max(a[i], cur + a[i]);
//     ans = max(ans, cur);
//
// 什么时候该「重新开始」？当 cur 已经变成负数时 ——
// 一个负数的前缀只会拖累后面，不如扔掉。
//
// ============ 为什么这一章要放一份「比分治还快」的代码 ============
//
// 因为它诚实：**分治不是万能的，这道题有更好的做法。**
//
// 学分治的价值在于「跨越中点怎么算」这套思维，它在很多题上是唯一出路
// （比如平面最近点对）。但具体到最大子段和，O(n) 的扫描完胜。
//
// **拿到题先想有没有更简单的办法，再考虑上工具。**
//
// 顺带一提：上面那两行其实就是动态规划 —— cur 是「以 i 结尾」这个状态，
// 那个 max 就是状态转移方程。第 21 章会正式介绍它。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    if (n <= 0) { cout << 0 << "\n"; return 0; }

    long long best = LLONG_MIN, cur = 0;
    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        cur = max(x, cur + x);      // 要么接着延，要么从 x 重新开始
        best = max(best, cur);
    }

    cout << best << "\n";
    return 0;
}

// 最大子段和 —— 分治
//
// 输入输出和 maxsubBrute.cpp 完全一样。
//
// 分治三步（第 11 章那个框架，一模一样）：
//
//   最大子段  =  三者取最大：
//       ① 完全落在左半边的     → 递归解决
//       ② 完全落在右半边的     → 递归解决
//       ③ **跨过中点的**       → 这才是要动脑的部分
//
// 跨过中点的那一段长什么样？它必然是
//     「左半边里以 mid 结尾的某一段」 + 「右半边里以 mid+1 开头的某一段」。
//
// 这两截可以各自 O(长度) 地扫出来：
//     从 mid 往左走，一路累加，记住最大值 → 左边最好的后缀
//     从 mid+1 往右走，一路累加，记住最大值 → 右边最好的前缀
// 两个加起来就是跨越中点的最优解。
//
// ⚠ 这两截都**必须非空**（至少含 mid 和 mid+1 各一个元素），
//   否则「跨过中点」这个前提就不成立了，会和 ①② 重复。
//
// 复杂度：T(n) = 2T(n/2) + O(n) —— 和归并排序一模一样，所以是 O(n log n)。

#include <bits/stdc++.h>
using namespace std;

vector<long long> a;

long long solve(int l, int r) {
    if (l == r) return a[l];                    // 边界：只剩一个元素

    int mid = l + (r - l) / 2;
    long long best = max(solve(l, mid), solve(mid + 1, r));    // ①②

    // ③ 跨过中点：左边最好的后缀 + 右边最好的前缀
    long long sum = 0, leftBest = LLONG_MIN;
    for (int i = mid; i >= l; i--) { sum += a[i]; leftBest = max(leftBest, sum); }

    sum = 0;
    long long rightBest = LLONG_MIN;
    for (int i = mid + 1; i <= r; i++) { sum += a[i]; rightBest = max(rightBest, sum); }

    return max(best, leftBest + rightBest);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    if (n <= 0) { cout << 0 << "\n"; return 0; }

    a.assign(n, 0);
    for (int i = 0; i < n; i++) cin >> a[i];

    cout << solve(0, n - 1) << "\n";
    return 0;
}

// 第 k 小 —— 暴力：排完序再取
//
// 输入：第一行 n k，第二行 n 个整数
// 输出：从小到大数，第 k 个数是多少（k 从 1 开始）
//
// 排序 O(n log n)，然后 O(1) 取。
//
// 这份代码没什么可说的，而且**在比赛里通常够用** ——
// n = 10⁶ 时 sort 也就 0.1 秒。
//
// 但它做了多余的事：我们只想知道第 k 个是谁，
// 却把**所有** n 个数的顺序都排出来了。下一份代码只做必要的那部分。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    if (!(cin >> n >> k)) return 0;
    if (n <= 0 || k < 1 || k > n) { cout << 0 << "\n"; return 0; }

    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    sort(a.begin(), a.end());
    cout << a[k - 1] << "\n";
    return 0;
}

// 第 k 小 —— 快速选择（quickselect）
//
// 输入输出和 selectBrute.cpp 完全一样，但平均只要 O(n)。
//
// ============ 和快排的唯一区别：只递归一边 ============
//
// 快排划分完之后，基准就待在它最终的位置 p 上了：
//     左边全部 <= 基准，右边全部 >= 基准。
//
// 于是：
//     p == k-1  →  基准就是答案，直接返回
//     p >  k-1  →  第 k 小在左边，**只递归左边**
//     p <  k-1  →  第 k 小在右边，**只递归右边**
//
// 快排两边都要排，所以是 O(n log n)；
// 这里每次只走一边，工作量是 n + n/2 + n/4 + … = 2n，所以平均 **O(n)**。
//
// （等比数列求和：每次问题规模减半，总工作量只是第一次的两倍。
//   这个「只往一边走」的结构，其实第 8 章的二分就是它的极端版本 ——
//   二分每次只做 O(1) 的工作，所以是 O(log n)。）
//
// 这类「每次砍掉一部分、只在剩下的里面继续找」的做法，有个专门的名字叫**减治**
// （decrease and conquer），区别于两边都要处理的**分治**。
//
// ⚠ 和快排一样，基准必须随机选，否则会被有序数据卡成 O(n²)。
//
// 顺带一提：C++ 标准库里这个功能叫 nth_element(first, first + k - 1, last)，
// 比赛里直接用它就行 —— 但手写一遍能让你真正理解「只递归一边」这件事。

#include <bits/stdc++.h>
using namespace std;

vector<long long> a;
mt19937 rng(20241202u);

/** 返回 a[l..r] 里第 k 小的数（k 从 1 开始，相对这一段而言） */
long long quickSelect(int l, int r, int k) {
    if (l >= r) return a[l];

    int p = l + (int)(rng() % (unsigned)(r - l + 1));
    swap(a[l], a[p]);
    long long pivot = a[l];

    int i = l, j = r;
    while (i < j) {
        while (i < j && a[j] >= pivot) j--;
        while (i < j && a[i] <= pivot) i++;
        if (i < j) swap(a[i], a[j]);
    }
    swap(a[l], a[i]);                     // 基准归位到下标 i

    int leftLen = i - l + 1;              // 左半段（含基准）有几个数
    if (k == leftLen) return a[i];        // 基准就是第 k 小
    if (k < leftLen) return quickSelect(l, i - 1, k);          // 只走左边
    return quickSelect(i + 1, r, k - leftLen);                 // 只走右边
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    if (!(cin >> n >> k)) return 0;
    if (n <= 0 || k < 1 || k > n) { cout << 0 << "\n"; return 0; }

    a.assign(n, 0);
    for (int i = 0; i < n; i++) cin >> a[i];

    cout << quickSelect(0, n - 1, k) << "\n";
    return 0;
}

// 快速选择 —— 把「每次只走一边」打印出来
//
// 输入：n k / n 个整数（用小数据）
// 输出：每一轮的候选区间、选的基准、划分结果，以及往哪边走
//
// 跑一遍，盯住「还剩多少个候选」这个数字：
//   它大致是 n → n/2 → n/4 → … 一路减半。
//
// 加起来 n + n/2 + n/4 + … ≈ 2n，所以平均是 O(n)。
// **每次只走一边，总工作量只是第一次的两倍** —— 这就是减治的威力。
//
// 对比一下快排：它两边都要走，所以每一层的总量都还是 n，共 log n 层。

#include <bits/stdc++.h>
using namespace std;

vector<long long> a;
mt19937 rng(20241203u);
int rounds = 0, totalWork = 0;

void show(int l, int r, int i) {
    cout << "      [";
    for (int p = l; p <= r; p++) {
        if (p == i) cout << "(" << a[p] << ")";
        else cout << a[p];
        cout << (p == r ? "" : " ");
    }
    cout << "]\n";
}

long long quickSelect(int l, int r, int k) {
    if (l >= r) {
        cout << "  区间只剩一个数 " << a[l] << " —— 它就是答案\n";
        return a[l];
    }

    rounds++;
    totalWork += r - l + 1;
    cout << "  第 " << rounds << " 轮：候选区间 [" << l << ", " << r << "]，还剩 "
         << (r - l + 1) << " 个候选，要找其中第 " << k << " 小\n";

    int p = l + (int)(rng() % (unsigned)(r - l + 1));
    swap(a[l], a[p]);
    long long pivot = a[l];
    cout << "      随机选基准 = " << pivot << "\n";

    int i = l, j = r;
    while (i < j) {
        while (i < j && a[j] >= pivot) j--;
        while (i < j && a[i] <= pivot) i++;
        if (i < j) swap(a[i], a[j]);
    }
    swap(a[l], a[i]);

    cout << "      划分后（括号里是基准，它已经在最终位置上了）：\n";
    show(l, r, i);

    int leftLen = i - l + 1;
    if (k == leftLen) {
        cout << "      基准正好是第 " << k << " 小 —— 答案就是它\n";
        return a[i];
    }
    if (k < leftLen) {
        cout << "      第 " << k << " 小在基准左边 → 只递归左边，右边 "
             << (r - i) << " 个数**再也不看了**\n";
        return quickSelect(l, i - 1, k);
    }
    cout << "      第 " << k << " 小在基准右边 → 只递归右边，左边 "
         << leftLen << " 个数**再也不看了**\n";
    return quickSelect(i + 1, r, k - leftLen);
}

int main() {
    int n, k;
    if (!(cin >> n >> k)) return 0;
    if (n <= 0 || n > 30 || k < 1 || k > n) { cout << "这份是用来看过程的，请用 1 <= k <= n <= 30\n"; return 0; }

    a.assign(n, 0);
    for (int i = 0; i < n; i++) cin >> a[i];

    cout << "数组：";
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << "　要找第 " << k << " 小\n\n";

    long long ans = quickSelect(0, n - 1, k);

    cout << "\n答案 = " << ans << "\n";
    cout << "一共 " << rounds << " 轮，累计处理了 " << totalWork << " 个元素（n = " << n
         << "，注意它接近 2n 而不是 n·log n）\n";
    return 0;
}

// 第 k 小 —— 快速选择（quickselect）
//
// 输入输出和 selectBrute.cpp 完全一样，但平均只要 O(n)。
//
// ============ 和快排的唯一区别：只递归一边 ============
//
// 快排划分完之后，基准就待在它最终的位置 p 上了：
//     左边全部 <= 基准，右边全部 >= 基准。
//
// 于是：
//     p == k-1  →  基准就是答案，直接返回
//     p >  k-1  →  第 k 小在左边，**只递归左边**
//     p <  k-1  →  第 k 小在右边，**只递归右边**
//
// 快排两边都要排，所以是 O(n log n)；
// 这里每次只走一边，工作量是 n + n/2 + n/4 + … = 2n，所以平均 **O(n)**。
//
// （等比数列求和：每次问题规模减半，总工作量只是第一次的两倍。
//   这个「只往一边走」的结构，其实第 8 章的二分就是它的极端版本 ——
//   二分每次只做 O(1) 的工作，所以是 O(log n)。）
//
// 这类「每次砍掉一部分、只在剩下的里面继续找」的做法，有个专门的名字叫**减治**
// （decrease and conquer），区别于两边都要处理的**分治**。
//
// ⚠ 和快排一样，基准必须随机选，否则会被有序数据卡成 O(n²)。
//
// 顺带一提：C++ 标准库里这个功能叫 nth_element(first, first + k - 1, last)，
// 比赛里直接用它就行 —— 但手写一遍能让你真正理解「只递归一边」这件事。

#include <bits/stdc++.h>
using namespace std;

vector<long long> a;
mt19937 rng(20241202u);

/** 返回 a[l..r] 里第 k 小的数（k 从 1 开始，相对这一段而言） */
long long quickSelect(int l, int r, int k) {
    if (l >= r) return a[l];

    int p = l + (int)(rng() % (unsigned)(r - l + 1));
    swap(a[l], a[p]);
    long long pivot = a[l];

    int i = l, j = r;
    while (i < j) {
        while (i < j && a[j] >= pivot) j--;
        while (i < j && a[i] <= pivot) i++;
        if (i < j) swap(a[i], a[j]);
    }
    swap(a[l], a[i]);                     // 基准归位到下标 i

    int leftLen = i - l + 1;              // 左半段（含基准）有几个数
    if (k == leftLen) return a[i];        // 基准就是第 k 小
    if (k < leftLen) return quickSelect(l, i - 1, k);          // 只走左边
    return quickSelect(i + 1, r, k - leftLen);                 // 只走右边
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    if (!(cin >> n >> k)) return 0;
    if (n <= 0 || k < 1 || k > n) { cout << 0 << "\n"; return 0; }

    a.assign(n, 0);
    for (int i = 0; i < n; i++) cin >> a[i];

    cout << quickSelect(0, n - 1, k) << "\n";
    return 0;
}