阜城网站建设公司,seo发帖网站,WordPress 黛米付,搭建本地网站买卖股票的最佳时机 III 假设你有一个数组#xff0c;它的第i个元素是一支给定的股票在第i天的价格。设计一个算法来找到最大的利润。你最多可以完成两笔交易。 样例 给出一个样例数组 [4,4,6,1,1,4,2,5], 返回 6 解题 尝试参考买卖股票的最佳时机 II 提交运行发现错误#…买卖股票的最佳时机 III 假设你有一个数组它的第i个元素是一支给定的股票在第i天的价格。设计一个算法来找到最大的利润。你最多可以完成两笔交易。 样例 给出一个样例数组 [4,4,6,1,1,4,2,5], 返回 6 解题 尝试参考买卖股票的最佳时机 II 提交运行发现错误每次找到连续的递增子数组记录前后的差值找到两个最大的。如下程序其实有问题最大的差值可能跨两个子数组的。 如{1,2,4,2,5,7,2,4,9,0} 三个递增数组{1,2,4}、{2,5,7}、{2,4,9}起始数组的差是3、5、7最大两个和是;57 12 然后对前两数组第二个数组的起始数大于第一个的起始数而第二个的结束数大于第一个的结束数通过递增子数组还大于2个所有有个更大的其实数组差是7-1 6. public int maxProfit(int[] A) {// write your code hereif(A null || A.length 0)return 0;if(A.length 1)return 0;int sum0;int i 0;int j 0;int subSum1 Integer.MIN_VALUE;int subSum2 Integer.MIN_VALUE;int tmpSum 0;while(i A.length j A.length){tmpSum 0;while(jA.length-1 A[j] A[j1])j;tmpSum A[j] - A[i];if(subSum1 subSum2){ // subSum1 是较小者int tmp subSum1;subSum1 subSum2;subSum2 tmp;}// 当 tmpSum 比较小 subSum1 大 的时候更新sumSum1if(tmpSum subSum1){subSum1 tmpSum;}i j 1;// 下一个位置从新开始j j 1;}if( subSum2 Integer.MIN_VALUE)return subSum1;return subSum1 subSum2;} View Code 题目标签中有个前后遍历就想到定义两个数组 left[i] 表示0 - i 并且i是卖出的最大收益 right[i] 表示i - A.length-1 并且i 是买入的最大收益 最后求两个数组的最大和但是这里时间复杂度是O(N^2)可以进一步的降低的 class Solution {/*** param prices: Given an integer array* return: Maximum profit*/public int maxProfit(int[] A) {// write your code hereif(A null || A.length 0)return 0;if(A.length 1)return 0;int sum0;int[] left new int[A.length];int[] right new int[A.length];int min A[0];// left[i] 表示在 0 - i 中能够 卖出的最大收益当是 0的时候表示不买也不卖for(int i 1;i A.length;i){if(min A[i]){left[i] A[i] - min;}elsemin A[i];}int max A[A.length - 1];// right[i] 表示在 i - A.length-1 中能够卖出的最大收益for( int i A.length -2;i0;i--){if(max A[i]){right[i] max - A[i];}else{max A[i];}}max Integer.MIN_VALUE;for(int i 0;i A.length;i){for(int j i;jA.length;j)max Math.max(max,left[i] right[j]);}return max;}
}; 如果我们更改定义的两个数组 left[i] 表示0 - i 这段数组的最大收益 right[i] 表示i - A.length-1 这段数组的最大收益 在求两个数组的和时候只需要线性的时间复杂度 class Solution {/*** param prices: Given an integer array* return: Maximum profit*/public int maxProfit(int[] A) {// write your code hereif(A null || A.length 0)return 0;if(A.length 1)return 0;int sum0;int[] left new int[A.length];int[] right new int[A.length];int min A[0];// left[i] 表示在 0 - i 中能够 卖出的最大收益当是 0的时候表示不买也不卖for(int i 1;i A.length;i){if(min A[i]){left[i] Math.max(left[i-1], A[i] - min);}else{left[i] left[i-1];min A[i];}}int max A[A.length - 1];// right[i] 表示在 i - A.length-1 中能够卖出的最大收益for( int i A.length -2;i0;i--){if(max A[i]){right[i] Math.max(right[i1],max - A[i]);}else{right[i] right[i1];max A[i];}}max Integer.MIN_VALUE;for(int i 0;i A.length;i){max Math.max(max,left[i] right[i]);}return max;}
};
