public class 一维数组前缀和 { publicstaticvoidmain(String[] args) { Scannerscan=newScanner(System.in); int num[]=newint[] {1,2,3,4,5,6,7,8,9,10};//目标数组 int sum[]=newint[11];//前缀和(差分数组)开long,切记,切记!这里不开了嫌麻烦 for (inti=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 (inti=0; i <num.length; i++) { ans+=num[i]; } System.out.println(ans); scan.close(); } }
import java.util.Scanner; publicclassp1115最大子段和 { publicstaticvoidmain(String[] args) { Scannerscan=newScanner(System.in); int n=scan.nextInt(); int ans=Integer.MIN_VALUE;//返回值是最大字段和,初始化为integer最小值 int sum_num[]=newint[n+1]; for (inti=1; i <=n; i++) {//初步思路,前缀和+dp sum_num[i]=sum_num[i-1]+scan.nextInt(); } for (inti=1; i <n+1; i++) { for (intj= 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(); } }