AcWing 1059. 股票买卖 VI Java优化版
原题链接
中等
作者:
小赵想滑板
,
2024-01-24 11:57:44
,
所有人可见
,
阅读 90
时间复杂度O(n) 空间复杂度O(n) 代码
import java.util.*;
public class Main{
public static void main(String[]args){
Scanner sc=new Scanner(System.in);
int N=100010,T=0x3f3f3f;
int n,m;
int w[]=new int [N];
int f[][]=new int[2][N];
n=sc.nextInt();
m=sc.nextInt();
for(int i=1;i<=n;i++) w[i]=sc.nextInt();
Arrays.fill(f[0],-T);
Arrays.fill(f[1],-T);
for(int i=0;i<=n;i++) f[0][i]=0;
for(int i=1;i<=n;i++)
{
f[0][i]=Math.max(f[0][i-1],f[1][i-1]+w[i]);
f[1][i]=Math.max(f[1][i-1],f[0][i-1]-w[i]-m);
}
System.out.println(f[0][n]);
}
}
将空间复杂度优化为 O(1) 代码
import java.util.*;
public class Main{
public static void main(String[]args){
Scanner sc=new Scanner(System.in);
int n,m,w;
int f0=0,f1=0;
n=sc.nextInt();
m=sc.nextInt();
w=sc.nextInt();
f1=-w;//若是持仓状态 一定已经花钱买进股票了;
for(int i=2;i<=n;i++){
w=sc.nextInt();
f0=Math.max(f0,f1+w-m);
f1=Math.max(f1,f0-w);
}
System.out.println(f0);
}
}