Problem Description

Given a sequence of n integers a, find the maximum sum of any contiguous non-empty subarray.

Input Specificatino

The first line contains integer n indicating the sequence length. The second line contains n integers representing the sequence elements. Constraints: 1 ≤ n ≤ 2×10⁵, -10⁴ ≤ aᵢ ≤ 10⁴

Output Specification

Output a single integer representing the maximum subarray sum.

Example

Input: [2, -4, 3, -1, 2, -4, 3] Output: 4 Explanation: The subarray [3, -1, 2] yields the maximum sum of 4.

Dynamic Programmming Solution

#include <iostream>
#include <algorithm>
using namespace std;

const int MAX_LEN = 200005;
int sequence[MAX_LEN];
int dp[MAX_LEN];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> sequence[i];
    }
    
    dp[0] = sequence[0];
    for (int i = 1; i < n; i++) {
        dp[i] = max(sequence[i], dp[i-1] + sequence[i]);
    }
    
    int result = dp[0];
    for (int i = 1; i < n; i++) {
        result = max(result, dp[i]);
    }
    cout << result << endl;
    return 0;
}

Divide and Conquer Solution

#include <iostream>
#include <algorithm>
using namespace std;

struct SegmentData {
    int total;
    int max_prefix;
    int max_suffix;
    int max_subarray;
};

const int MAX_SIZE = 200005;
int arr[MAX_SIZE];
SegmentData tree[4 * MAX_SIZE];

SegmentData combine(SegmentData left, SegmentData right) {
    SegmentData merged;
    merged.total = left.total + right.total;
    merged.max_prefix = max(left.max_prefix, left.total + right.max_prefix);
    merged.max_suffix = max(right.max_suffix, left.max_suffix + right.total);
    merged.max_subarray = max({left.max_subarray, right.max_subarray, 
                             left.max_suffix + right.max_prefix});
    return merged;
}

void build_tree(int idx, int low, int high) {
    if (low == high) {
        tree[idx] = {arr[low], arr[low], arr[low], arr[low]};
        return;
    }
    
    int mid = (low + high) / 2;
    build_tree(2*idx, low, mid);
    build_tree(2*idx+1, mid+1, high);
    tree[idx] = combine(tree[2*idx], tree[2*idx+1]);
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    build_tree(1, 0, n-1);
    cout << tree[1].max_subarray << endl;
    return 0;
}