动态规划---观察优化枚举(股票系列问题)

 

 
  
   121. 买卖股票的最佳机遇 - 力扣（LeetCode）

1. public class Code01_Stock1 {
3.         public static int maxProfit(int[] prices) {
4.                 int ans = 0;
5.                 for (int i = 1, min = prices[0]; i < prices.length; i++) {
6.                         // min : 0...i范围上的最小值
7.                         min = Math.min(min, prices[i]);
8.                         ans = Math.max(ans, prices[i] - min);
9.                 }
10.                 return ans;
11.         }
13. }

复制代码

 从0 - i上的最大利润：在i天的时候卖，必要0-i上的最小值；不在i上卖，则必要0 - i-1天上的最大利润，比较即可



122. 买卖股票的最佳机遇 II - 力扣（LeetCode）

1. public class Code02_Stock2 {
3.         public static int maxProfit(int[] prices) {
4.                 int ans = 0;
5.                 for (int i = 1; i < prices.length; i++) {
6.                         ans += Math.max(prices[i] - prices[i - 1], 0);
7.                 }
8.                 return ans;
9.         }
11. }

复制代码

只要两天之间的差值为正数，即有利润，就购买；否则不买



  123. 买卖股票的最佳机遇 III - 力扣（LeetCode）

1. public class Code03_Stock3 {
3.         // 完全不优化枚举的方法
4.         // 通过不了，会超时
5.         public static int maxProfit1(int[] prices) {
6.                 int n = prices.length;
7.                 // dp1[i] : 0...i范围上发生一次交易，不要求在i的时刻卖出，最大利润是多少
8.                 int[] dp1 = new int[n];
9.                 for (int i = 1, min = prices[0]; i < n; i++) {
10.                         min = Math.min(min, prices[i]);
11.                         dp1[i] = Math.max(dp1[i - 1], prices[i] - min);
12.                 }
13.                 // dp2[i] : 0...i范围上发生两次交易，并且第二次交易在i时刻卖出，最大利润是多少
14.                 int[] dp2 = new int[n];
15.                 int ans = 0;
16.                 for (int i = 1; i < n; i++) {
17.                         // 第二次交易一定要在i时刻卖出
18.                         for (int j = 0; j <= i; j++) {
19.                                 // 枚举第二次交易的买入时机j <= i
20.                                 dp2[i] = Math.max(dp2[i], dp1[j] + prices[i] - prices[j]);
21.                         }
22.                         ans = Math.max(ans, dp2[i]);
23.                 }
24.                 return ans;
25.         }
27.         // 观察出优化枚举的方法
28.         // 引入best数组，需要分析能力
29.         public static int maxProfit2(int[] prices) {
30.                 int n = prices.length;
31.                 // dp1[i] : 0...i范围上发生一次交易，不要求在i的时刻卖出，最大利润是多少
32.                 int[] dp1 = new int[n];
33.                 for (int i = 1, min = prices[0]; i < n; i++) {
34.                         min = Math.min(min, prices[i]);
35.                         dp1[i] = Math.max(dp1[i - 1], prices[i] - min);
36.                 }
37.                 // best[i] : 0...i范围上，所有的dp1[i]-prices[i]，最大值是多少
38.                 // 这是数组的设置完全是为了替代最后for循环的枚举行为
39.                 int[] best = new int[n];
40.                 best[0] = dp1[0] - prices[0];
41.                 for (int i = 1; i < n; i++) {
42.                         best[i] = Math.max(best[i - 1], dp1[i] - prices[i]);
43.                 }
44.                 // dp2[i] : 0...i范围上发生两次交易，并且第二次交易在i时刻卖出，最大利润是多少
45.                 int[] dp2 = new int[n];
46.                 int ans = 0;
47.                 for (int i = 1; i < n; i++) {
48.                         // 不需要枚举了
49.                         // 因为，best[i]已经揭示了，0...i范围上，所有的dp1[i]-prices[i]，最大值是多少
50.                         dp2[i] = best[i] + prices[i];
51.                         ans = Math.max(ans, dp2[i]);
52.                 }
53.                 return ans;
54.         }
56.         // 发现所有更新行为都可以放在一起
57.         // 并不需要写多个并列的for循环
58.         // 就是等义改写，不需要分析能力
59.         public static int maxProfit3(int[] prices) {
60.                 int n = prices.length;
61.                 int[] dp1 = new int[n];
62.                 int[] best = new int[n];
63.                 best[0] = -prices[0];
64.                 int[] dp2 = new int[n];
65.                 int ans = 0;
66.                 for (int i = 1, min = prices[0]; i < n; i++) {
67.                         min = Math.min(min, prices[i]);
68.                         dp1[i] = Math.max(dp1[i - 1], prices[i] - min);
69.                         best[i] = Math.max(best[i - 1], dp1[i] - prices[i]);
70.                         dp2[i] = best[i] + prices[i];
71.                         ans = Math.max(ans, dp2[i]);
72.                 }
73.                 return ans;
74.         }
76.         // 发现只需要有限几个变量滚动更新下去就可以了
77.         // 空间压缩的版本
78.         // 就是等义改写，不需要分析能力
79.         public static int maxProfit4(int[] prices) {
80.                 int dp1 = 0;
81.                 int best = -prices[0];
82.                 int ans = 0;
83.                 for (int i = 1, min = prices[0]; i < prices.length; i++) {
84.                         min = Math.min(min, prices[i]);
85.                         dp1 = Math.max(dp1, prices[i] - min);
86.                         best = Math.max(best, dp1 - prices[i]);
87.                         ans = Math.max(ans, best + prices[i]); // ans = Math.max(ans, dp2);
88.                 }
89.                 return ans;
90.         }
92. }

复制代码

188. 买卖股票的最佳机遇 IV - 力扣（LeetCode）

1. public class Code04_Stock4 {
3.         // 就是股票问题2
4.         public static int free(int[] prices) {
5.                 int ans = 0;
6.                 for (int i = 1; i < prices.length; i++) {
7.                         ans += Math.max(prices[i] - prices[i - 1], 0);
8.                 }
9.                 return ans;
10.         }
12.         public static int maxProfit1(int k, int[] prices) {
13.                 int n = prices.length;
14.                 if (k >= n / 2) {
15.                         // 这是一个剪枝
16.                         // 如果k >= n / 2，那么代表所有上坡都可以抓到
17.                         // 所有上坡都可以抓到 == 交易次数无限，所以回到股票问题2
18.                         return free(prices);
19.                 }
20.                 int[][] dp = new int[k + 1][n];
21.                 for (int i = 1; i <= k; i++) {
22.                         for (int j = 1; j < n; j++) {
23.                                 dp[i][j] = dp[i][j - 1];
24.                                 for (int p = 0; p < j; p++) {
25.                                         dp[i][j] = Math.max(dp[i][j], dp[i - 1][p] + prices[j] - prices[p]);
26.                                 }
27.                         }
28.                 }
29.                 return dp[k][n - 1];
30.         }
32.         public static int maxProfit2(int k, int[] prices) {
33.                 int n = prices.length;
34.                 if (k >= n / 2) {
35.                         // 这是一个剪枝
36.                         // 如果k >= n / 2，那么代表所有上坡都可以抓到
37.                         // 所有上坡都可以抓到 == 交易次数无限，所以回到股票问题2
38.                         return free(prices);
39.                 }
40.                 int[][] dp = new int[k + 1][n];
41.                 for (int i = 1, best; i <= k; i++) {
42.                         best = dp[i - 1][0] - prices[0];
43.                         for (int j = 1; j < n; j++) {
44.                                 // 用best变量替代了枚举行为
45.                                 dp[i][j] = Math.max(dp[i][j - 1], best + prices[j]);
46.                                 best = Math.max(best, dp[i - 1][j] - prices[j]);
47.                         }
48.                 }
49.                 return dp[k][n - 1];
50.         }
52.         // 对方法2进行空间压缩的版本
53.         public static int maxProfit3(int k, int[] prices) {
54.                 int n = prices.length;
55.                 if (k >= n / 2) {
56.                         // 这是一个剪枝
57.                         // 如果k >= n / 2，那么代表所有上坡都可以抓到
58.                         // 所有上坡都可以抓到 == 交易次数无限，所以回到股票问题2
59.                         return free(prices);
60.                 }
61.                 int[] dp = new int[n];
62.                 for (int i = 1, best, tmp; i <= k; i++) {
63.                         best = dp[0] - prices[0];
64.                         for (int j = 1; j < n; j++) {
65.                                 tmp = dp[j];
66.                                 dp[j] = Math.max(dp[j - 1], best + prices[j]);
67.                                 best = Math.max(best, tmp - prices[j]);
68.                         }
69.                 }
70.                 return dp[n - 1];
71.         }
73. }

复制代码

 dp[j]表示从0-j天最多买卖i次所能获得的最大收益
 


714. 买卖股票的最佳机遇含手续费 - 力扣（LeetCode）

1. public class Code05_Stack5 {
3.         public static int maxProfit(int[] prices, int fee) {
4.                 // prepare : 交易次数无限制情况下，获得收益的同时扣掉了一次购买和手续费之后，最好的情况
5.                 int prepare = -prices[0] - fee;
6.                 // done : 交易次数无限制情况下，能获得的最大收益
7.                 int done = 0;
8.                 for (int i = 1; i < prices.length; i++) {
9.                         done = Math.max(done, prepare + prices[i]);
10.                         prepare = Math.max(prepare, done - prices[i] - fee);
11.                 }
12.                 return done;
13.         }
15. }

复制代码

手续费无非是在卖出的时候多出一笔钱，所以和无限次购买股票是一样的



 309. 买卖股票的最佳机遇含冷冻期 - 力扣（LeetCode）

 

1. public class Code06_Stack6 {
3.         public static int maxProfit1(int[] prices) {
4.                 int n = prices.length;
5.                 if (n < 2) {
6.                         return 0;
7.                 }
8.                 // prepare[i] : 0...i范围上，可以做无限次交易，获得收益的同时一定要扣掉一次购买，所有情况中的最好情况
9.                 int[] prepare = new int[n];
10.                 // done[i] : 0...i范围上，可以做无限次交易，能获得的最大收益
11.                 int[] done = new int[n];
12.                 prepare[1] = Math.max(-prices[0], -prices[1]);
13.                 done[1] = Math.max(0, prices[1] - prices[0]);
14.                 for (int i = 2; i < n; i++) {
15.                         done[i] = Math.max(done[i - 1], prepare[i - 1] + prices[i]);
16.                         prepare[i] = Math.max(prepare[i - 1], done[i - 2] - prices[i]);
17.                 }
18.                 return done[n - 1];
19.         }
21.         // 只是把方法1做了变量滚动更新(空间压缩)
22.         // 并没有新的东西
23.         public static int maxProfit2(int[] prices) {
24.                 int n = prices.length;
25.                 if (n < 2) {
26.                         return 0;
27.                 }
28.                 // prepare : prepare[i-1]
29.                 int prepare = Math.max(-prices[0], -prices[1]);
30.                 // done2 : done[i-2]
31.                 int done2 = 0;
32.                 // done1 : done[i-1]
33.                 int done1 = Math.max(0, prices[1] - prices[0]);
34.                 for (int i = 2, curDone; i < n; i++) {
35.                         // curDone : done[i]
36.                         curDone = Math.max(done1, prepare + prices[i]);
37.                         // prepare : prepare[i-1] -> prepare[i]
38.                         prepare = Math.max(prepare, done2 - prices[i]);
39.                         done2 = done1;
40.                         done1 = curDone;
41.                 }
42.                 return done1;
43.         }
45. }

复制代码

 


  903. DI 序列的有效排列 - 力扣（LeetCode）

1. public class Solution {
3.         public static int numPermsDISequence1(String s) {
4.                 return f(s.toCharArray(), 0, s.length() + 1, s.length() + 1);
5.         }
7.         // 猜法很妙！
8.         // 一共有n个数字，位置范围0~n-1
9.         // 当前来到i位置，i-1位置的数字已经确定，i位置的数字还没确定
10.         // i-1位置和i位置的关系，是s[i-1] : D、I
11.         // 0~i-1范围上是已经使用过的数字，i个
12.         // 还没有使用过的数字中，比i-1位置的数字小的，有less个
13.         // 还没有使用过的数字中，比i-1位置的数字大的，有n - i - less个
14.         // 返回后续还有多少种有效的排列
15.         public static int f(char[] s, int i, int less, int n) {
16.                 int ans = 0;
17.                 if (i == n) {
18.                         ans = 1;
19.                 } else if (i == 0 || s[i - 1] == 'D') {
20.                         for (int nextLess = 0; nextLess < less; nextLess++) {
21.                                 ans += f(s, i + 1, nextLess, n);
22.                         }
23.                 } else {
24.                         for (int nextLess = less, k = 1; k <= n - i - less; k++, nextLess++) {
25.                                 ans += f(s, i + 1, nextLess, n);
26.                         }
27.                 }
28.                 return ans;
29.         }
31.         public static int numPermsDISequence2(String str) {
32.                 int mod = 1000000007;
33.                 char[] s = str.toCharArray();
34.                 int n = s.length + 1;
35.                 int[][] dp = new int[n + 1][n + 1];
36.                 for (int less = 0; less <= n; less++) {
37.                         dp[n][less] = 1;
38.                 }
39.                 for (int i = n - 1; i >= 0; i--) {
40.                         for (int less = 0; less <= n; less++) {
41.                                 if (i == 0 || s[i - 1] == 'D') {
42.                                         for (int nextLess = 0; nextLess < less; nextLess++) {
43.                                                 dp[i][less] = (dp[i][less] + dp[i + 1][nextLess]) % mod;
44.                                         }
45.                                 } else {
46.                                         for (int nextLess = less, k = 1; k <= n - i - less; k++, nextLess++) {
47.                                                 dp[i][less] = (dp[i][less] + dp[i + 1][nextLess]) % mod;
48.                                         }
49.                                 }
50.                         }
51.                 }
52.                 return dp[0][n];
53.         }
55.         // 通过观察方法2，得到优化枚举的方法
56.         public static int numPermsDISequence(String str) {
57.                 int mod = 1000000007;
58.                 char[] s = str.toCharArray();
59.                 int n = s.length + 1;
60.                 int[][] dp = new int[n + 1][n + 1];
61.                 for (int less = 0; less <= n; less++) {
62.                         dp[n][less] = 1;
63.                 }
64.                 for (int i = n - 1; i >= 0; i--) {
65.                         if (i == 0 || s[i - 1] == 'D') {
66.                                 dp[i][1] = dp[i + 1][0];
67.                                 for (int less = 2; less <= n; less++) {
68.                                         dp[i][less] = (dp[i][less - 1] + dp[i + 1][less - 1]) % mod;
69.                                 }
70.                         } else {
71.                                 dp[i][n - i - 1] = dp[i + 1][n - i - 1];
72.                                 for (int less = n - i - 2; less >= 0; less--) {
73.                                         dp[i][less] = (dp[i][less + 1] + dp[i + 1][less]) % mod;
74.                                 }
75.                         }
76.                 }
77.                 return dp[0][n];
78.         }
80. }

复制代码

1235. 规划兼职工作 - 力扣（LeetCode）


 

1. public class Code01_MaximumProfitInJobScheduling {
3.         public static int MAXN = 50001;
5.         public static int[][] jobs = new int[MAXN][3];
7.         public static int[] dp = new int[MAXN];
9.         public static int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
10.                 int n = startTime.length;
11.                 for (int i = 0; i < n; i++) {
12.                         jobs[i][0] = startTime[i];
13.                         jobs[i][1] = endTime[i];
14.                         jobs[i][2] = profit[i];
15.                 }
16.                 // 工作按照结束时间从小到大排序
17.                 Arrays.sort(jobs, 0, n, (a, b) -> a[1] - b[1]);
18.                 dp[0] = jobs[0][2];
19.                 for (int i = 1, start; i < n; i++) {
20.                         start = jobs[i][0];
21.                         dp[i] = jobs[i][2];
22.                         if (jobs[0][1] <= start) {
23.                                 dp[i] += dp[find(i - 1, start)];
24.                         }
25.                         dp[i] = Math.max(dp[i], dp[i - 1]);
26.                 }
27.                 return dp[n - 1];
28.         }
30.         // job[0...i]范围上，找到结束时间 <= start，最右的下标
31.         public static int find(int i, int start) {
32.                 int ans = 0;
33.                 int l = 0;
34.                 int r = i;
35.                 int m;
36.                 while (l <= r) {
37.                         m = (l + r) / 2;
38.                         if (jobs[m][1] <= start) {
39.                                 ans = m;
40.                                 l = m + 1;
41.                         } else {
42.                                 r = m - 1;
43.                         }
44.                 }
45.                 return ans;
46.         }
48. }

复制代码

按照结束时间从小到大排序，才不会错过最大的利益



629. K 个逆序对数组 - 力扣（LeetCode）

1. public class Solution {
3.         // 最普通的动态规划
4.         // 不优化枚举
5.         public static int kInversePairs1(int n, int k) {
6.                 int mod = 1000000007;
7.                 // dp[i][j] : 1、2、3...i这些数字，形成的排列一定要有j个逆序对，请问这样的排列有几种
8.                 int[][] dp = new int[n + 1][k + 1];
9.                 dp[0][0] = 1;
10.                 for (int i = 1; i <= n; i++) {
11.                         dp[i][0] = 1;
12.                         for (int j = 1; j <= k; j++) {
13.                                 if (i > j) {
14.                                         for (int p = 0; p <= j; p++) {
15.                                                 dp[i][j] = (dp[i][j] + dp[i - 1][p]) % mod;
16.                                         }
17.                                 } else {
18.                                         // i <= j
19.                                         for (int p = j - i + 1; p <= j; p++) {
20.                                                 dp[i][j] = (dp[i][j] + dp[i - 1][p]) % mod;
21.                                         }
22.                                 }
23.                         }
24.                 }
25.                 return dp[n][k];
26.         }
27.     public static int kInversePairs(int n, int k) {
28.                 int mod = 1000000007;
29.                 int[][] dp = new int[n + 1][k + 1];
30.                 dp[0][0] = 1;
31.                 // window : 窗口的累加和
32.                 for (int i = 1, window; i <= n; i++) {
33.                         dp[i][0] = 1;
34.                         window = 1;
35.                         for (int j = 1; j <= k; j++) {
36.                                 if (i > j) {
37.                                         window = (window + dp[i - 1][j]) % mod;
38.                                 } else {
39.                                         // i <= j
40.                                         window = ((window + dp[i - 1][j]) % mod - dp[i - 1][j - i] + mod) % mod;
41.                                 }
42.                                 dp[i][j] = window;
43.                         }
44.                 }
45.                 return dp[n][k];
46.         }
48. }

复制代码

 

514. 自由之路 - 力扣（LeetCode）

1. public class Solution {
3.         // 为了让所有语言的同学都可以理解
4.         // 不会使用任何java语言自带的数据结构
5.         // 只使用最简单的数组结构
6.         public static int MAXN = 101;
8.         public static int MAXC = 26;
10.         public static int[] ring = new int[MAXN];
12.         public static int[] key = new int[MAXN];
14.         public static int[] size = new int[MAXC];
16.         public static int[][] where = new int[MAXC][MAXN];
18.         public static int[][] dp = new int[MAXN][MAXN];
20.         public static int n, m;
22.         public static void build(String r, String k) {
23.                 for (int i = 0; i < MAXC; i++) {
24.                         size[i] = 0;
25.                 }
26.                 n = r.length();
27.                 m = k.length();
28.                 for (int i = 0, v; i < n; i++) {
29.                         v = r.charAt(i) - 'a';
30.                         where[v][size[v]++] = i;
31.                         ring[i] = v;
32.                 }
33.                 for (int i = 0; i < m; i++) {
34.                         key[i] = k.charAt(i) - 'a';
35.                 }
36.                 for (int i = 0; i < n; i++) {
37.                         for (int j = 0; j < m; j++) {
38.                                 dp[i][j] = -1;
39.                         }
40.                 }
41.         }
43.         public static int findRotateSteps(String r, String k) {
44.                 build(r, k);
45.                 return f(0, 0);
46.         }
48.         // 指针当前指着轮盘i位置的字符，要搞定key[j....]所有字符，最小代价返回
49.         public static int f(int i, int j) {
50.                 if (j == m) {
51.                         // key长度是m
52.                         // 都搞定
53.                         return 0;
54.                 }
55.                 if (dp[i][j] != -1) {
56.                         return dp[i][j];
57.                 }
58.                 int ans;
59.                 if (ring[i] == key[j]) {
60.                         // ring b
61.                         //      i
62.                         // key  b
63.                         //      j
64.                         ans = 1 + f(i, j + 1);
65.                 } else {
66.                         // 轮盘处在i位置，ring[i] != key[j]
67.                         // jump1 : 顺时针找到最近的key[j]字符在轮盘的什么位置
68.                         // distance1 : 从i顺时针走向jump1有多远
69.                         int jump1 = clock(i, key[j]);
70.                         int distance1 = (jump1 > i ? (jump1 - i) : (n - i + jump1));
71.                         // jump2 : 逆时针找到最近的key[j]字符在轮盘的什么位置
72.                         // distance2 : 从i逆时针走向jump2有多远
73.                         int jump2 = counterClock(i, key[j]);
74.                         int distance2 = (i > jump2 ? (i - jump2) : (i + n - jump2));
75.                         ans = Math.min(distance1 + f(jump1, j), distance2 + f(jump2, j));
76.                 }
77.                 dp[i][j] = ans;
78.                 return ans;
79.         }
81.         // 从i开始，顺时针找到最近的v在轮盘的什么位置
82.         public static int clock(int i, int v) {
83.                 int l = 0;
84.                 // size[v] : 属于v这个字符的下标有几个
85.                 int r = size[v] - 1, m;
86.                 // sorted[0...size[v]-1]收集了所有的下标，并且有序
87.                 int[] sorted = where[v];
88.                 int find = -1;
89.                 // 有序数组中，找>i尽量靠左的下标
90.                 while (l <= r) {
91.                         m = (l + r) / 2;
92.                         if (sorted[m] > i) {
93.                                 find = m;
94.                                 r = m - 1;
95.                         } else {
96.                                 l = m + 1;
97.                         }
98.                 }
99.                 // 找到了就返回
100.                 // 没找到，那i顺指针一定先走到最小的下标
101.                 return find != -1 ? sorted[find] : sorted[0];
102.         }
104.         public static int counterClock(int i, int v) {
105.                 int l = 0;
106.                 int r = size[v] - 1, m;
107.                 int[] sorted = where[v];
108.                 int find = -1;
109.                 // 有序数组中，找<i尽量靠右的下标
110.                 while (l <= r) {
111.                         m = (l + r) / 2;
112.                         if (sorted[m] < i) {
113.                                 find = m;
114.                                 l = m + 1;
115.                         } else {
116.                                 r = m - 1;
117.                         }
118.                 }
119.                 // 找到了就返回
120.                 // 没找到，那i逆指针一定先走到最大的下标
121.                 return find != -1 ? sorted[find] : sorted[size[v] - 1];
122.         }
124. }

复制代码

 未排序数组中累加和小于或等于给定值的最宗子数组长度_牛客题霸_牛客网 (nowcoder.com)

1. import java.io.BufferedReader;
2. import java.io.IOException;
3. import java.io.InputStreamReader;
4. import java.io.OutputStreamWriter;
5. import java.io.PrintWriter;
6. import java.io.StreamTokenizer;
8. // 至今的最优解，全网题解几乎都是我几年前讲的方法
9. public class Main {
11.     public static int MAXN = 100001;
13.     public static int[] nums = new int[MAXN];
15.     public static int[] minSums = new int[MAXN];
17.     public static int[] minSumEnds = new int[MAXN];
19.     public static int n, k;
21.     public static void main(String[] args) throws IOException {
22.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
23.         StreamTokenizer in = new StreamTokenizer(br);
24.         PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
25.         while (in.nextToken() != StreamTokenizer.TT_EOF) {
26.             n = (int) in.nval;
27.             in.nextToken();
28.             k = (int) in.nval;
29.             for (int i = 0; i < n; i++) {
30.                 in.nextToken();
31.                 nums[i] = (int) in.nval;
32.             }
33.             out.println(compute1());
34.         }
35.         out.flush();
36.         out.close();
37.         br.close();
38.     }
40.     public static int compute1() {
41.         int[] sums = new int[n + 1];
42.         for (int i = 0, sum = 0; i < n; i++) {
43.             // sum : 0...i范围上，这前i+1个数字的累加和
44.             sum += nums[i];
45.             // sums[i + 1] : 前i+1个，包括一个数字也没有的时候，所有前缀和中的最大值
46.             sums[i + 1] = Math.max(sum, sums[i]);
47.         }
48.         int ans = 0;
49.         for (int i = 0, sum = 0, pre, len; i < n; i++) {
50.             sum += nums[i];
51.             pre = find(sums, sum - k);
52.             len = pre == -1 ? 0 : i - pre + 1;
53.             ans = Math.max(ans, len);
54.         }
55.         return ans;
56.     }
58.     public static int find(int[] sums, int num) {
59.         int l = 0;
60.         int r = n;
61.         int m = 0;
62.         int ans = -1;
63.         while (l <= r) {
64.             m = (l + r) / 2;
65.             if (sums[m] >= num) {
66.                 ans = m;
67.                 r = m - 1;
68.             } else {
69.                 l = m + 1;
70.             }
71.         }
72.         return ans;
73.     }
75.     public static int compute2() {
76.         minSums[n - 1] = nums[n - 1];
77.         minSumEnds[n - 1] = n - 1;
78.         for (int i = n - 2; i >= 0; i--) {
79.             if (minSums[i + 1] < 0) {
80.                 minSums[i] = nums[i] + minSums[i + 1];
81.                 minSumEnds[i] = minSumEnds[i + 1];
82.             } else {
83.                 minSums[i] = nums[i];
84.                 minSumEnds[i] = i;
85.             }
86.         }
87.         int ans = 0;
88.         for (int i = 0, sum = 0, end = 0; i < n; i++) {
89.             while (end < n && sum + minSums[end] <= k) {
90.                 sum += minSums[end];
91.                 end = minSumEnds[end] + 1;
92.             }
93.             if (end > i) {
94.                 // 如果end > i，
95.                 // 窗口范围：i...end-1，那么窗口有效
96.                 ans = Math.max(ans, end - i);
97.                 sum -= nums[i];
98.             } else {
99.                 // 如果end == i，那么说明窗口根本没扩出来，代表窗口无效
100.                 // end来到i+1位置，然后i++了
101.                 // 继续以新的i位置做开头去扩窗口
102.                 end = i + 1;
103.             }
104.         }
105.         return ans;
106.     }
108. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。