前缀和

算法原理

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

• 每次查询时间复杂度为m，若查询n次，时间复杂度就为n*m，0复杂度太高
• 这时可以使用前缀和思想优化算法
• 前缀和仅需一次时间复杂度为On的预处理，后续查询时间复杂度为O1
• 本质是把每次运算结果记录在前缀和数组中，以空间换时间
• 前缀和数组数很大，开long！开long！！开long！！！

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最大子段和

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

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!不愧是我。