子区间问题

子区间问题将持续更新中……

目录

问题概述 

例题 

1.子区间和的最大值

问题概述 

子区间与子序列不同，它要求必须是从原区间中连续的取出一段，解决这类问题，最常用的方法就是前缀和与动态规划，也常常会结合哈希表，set集合等进行优化

例题 

1.子区间和的最大值

题目描述

Given an array of n integers, your task is to find the maximum sum of values in a contiguous, nonempty subarray.

输入

The first input line has an integer n(1 ≤ n ≤ 2*105): the size of the array.
The second line has n integers x1,x2,...,xn(-109 ≤ xi ≤ 109): the array values.

输出

Print one integer: the maximum subarray sum.

样例输入

8
-1 3 -2 5 3 -5 2 2

样例输出

9

思路：动态规划。用dp[i]记录以i为结尾的子区间的最大和，状态转移：两种情况：续在前一个数后面，dp[i]=dp[i-1]+x[i]；以i为开头重新开始一个数组dp[i]=x[i]，找最大值即可。

代码：

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll N=200010;
int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n;cin>>n;vector<ll>x(n+1,0),dp(n+1,0);//以i为结尾的子区间的最大值 ll ans=LLONG_MIN; for (int i=1;i<=n;i++){cin>>x[i];dp[i]=max(x[i],x[i]+dp[i-1]);ans=max(ans,dp[i]);}cout<<ans;
}