前缀和

前缀和

算法原理

在程序设计中,可能会有查询一个长度为x的数组的相连m位的和的需求

  • 每次查询时间复杂度为m,若查询n次,时间复杂度就为n*m,0复杂度太高
  • 这时可以使用前缀和思想优化算法
  • 前缀和仅需一次时间复杂度为On的预处理,后续查询时间复杂度为O1
  • 本质是把每次运算结果记录在前缀和数组中,以空间换时间
  • 前缀和数组数很大,开long!开long!!开long!!!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class 一维数组前缀和 {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int num[]=new int[] {1,2,3,4,5,6,7,8,9,10};//目标数组
int sum[]=new int[11];//前缀和(差分数组)开long,切记,切记!这里不开了嫌麻烦
for (int i = 0; i < 10; i++) {
sum[i+1]=num[i]+sum[i];
}
System.err.println(sum[10]);
System.err.println(sum[10]-sum[8]);//以On的时间复杂度计算了10+9
int ans=0;
for (int i = 0; i <num.length; i++) {
ans+=num[i];
}
System.out.println(ans);
scan.close();
}
}

算法应用

p1115最大子段和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.Scanner;
public class p1115最大子段和 {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n=scan.nextInt();
int ans=Integer.MIN_VALUE;//返回值是最大字段和,初始化为integer最小值
int sum_num[]=new int[n+1];
for (int i = 1; i <=n; i++) {//初步思路,前缀和+dp
sum_num[i]=sum_num[i-1]+scan.nextInt();
}
for (int i = 1; i <n+1; i++) {
for (int j = i-1; j>=0; j--) {//不能将0计入
int sum=sum_num[i]-sum_num[j];
ans=Math.max(sum, ans);
}
}
System.out.println(ans);
scan.close();
}
}
  • 该程序通过40%数据,仍需调优
  • 坐牢的时候想到了一个降低一半时间复杂的的优化方法:可以一边读入一边计算ans

妈的,寄!

还是过40

改变思路

想到使用线性DP
状态表示:DP[i]表示以第i位结尾时,最大子段和值
状态转移方程:DP[i]=MAX(DP[i-1]+a[i],a[i])转移为 加上下一个数 抛弃前面的数字以下一个数为首位计算子段 取最大 ,太过简单不再赘述
滚动数组优化:DP=MAX(DP+a[i],a[i])
优化空间复杂度,别忘了记录最大值
经过计算不会爆int

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int dp=0;
int ans=Integer.MIN_VALUE;
int n=scan.nextInt();
for (int i = 0; i < n; i++) {
int a=scan.nextInt();
dp=Math.max(dp+a, a);
ans=Math.max(ans, dp);
}
System.out.println(ans);
scan.close();
}
}

AC!不愧是我。芜湖


前缀和
https://fireworks258.github.io/2024/04/27/前缀和/
作者
Fireworks
发布于
2024年4月27日
许可协议