0
Help us understand the problem. What are the problem?

posted at

updated at

121 答え

まずは試しに単純な for loop のネスト。

Brute Force

public int maxProfit(int[] prices) {
		int maxProfit = 0;
		
		for(int i = 0; i < prices.length -1; i++) {
			for(int j = i + 1; j < prices.length; j++) {
				int tempProfit = prices[j] - prices[i];
				maxProfit = Math.max(maxProfit, tempProfit);
			}
		}
		return maxProfit;
	}

結果: TLE

解答

Window Sliding Technique

次はWindow Sliding Technique をつかう。
参考:
GeeksForGeeks
Kindson The Tech Pro

この方法は
loopの長さが固定されていることで計算量を減らせる。

詳しいことはURLに掲載されている。このサイトは、灰色Coderの自分でも結構わかりやすかった。

  1. (買値の)最小値
  2.  利益
    の値を用意。
	public int maxProfit(int[] prices) {
		int minimumPrice = Integer.MAX_VALUE;
		int maxProfit = 0;

		for (int i = 0; i < prices.length; i++) {
			if (prices[i] < minimumPrice) { // minimumPriceを更新する
				minimumPrice = prices[i];

			} else {//prices[i]の値がminimumPriceではないとき
				int profit = prices[i] - minimumPrice;// profitを出す
				maxProfit = Math.max(maxProfit, profit); //max関数で最大のprofitを求める
			}
		}
		return maxProfit;
	}

うーん難しい。
解説を見る限り大体はBrute Forceを試してからDP?を使っている印象があるので、まずはBrute Forceを試すのが吉かと思う。

間違えたほう

こっちは間違っていたが記録として残しておく。
最小値が最後に来た場合に間違える。

public int maxProfit(int[] prices) {
		int minimumPrice = Integer.MAX_VALUE;
		int maxProfit = 0;
		int minimumIndex = 0;

		for (int i = 0; i < prices.length; i++) {
			if (prices[i] < minimumPrice) {
				minimumIndex = i;
			}
			minimumPrice = Math.min(minimumPrice, prices[i]);
		}

		for (int i = minimumIndex; i < prices.length; i++) {
			maxProfit = Math.max(maxProfit, prices[i] - prices[minimumIndex]);
		}
		return maxProfit;

	}

Register as a new user and use Qiita more conveniently

  1. You can follow users and tags
  2. you can stock useful information
  3. You can make editorial suggestions for articles
What you can do with signing up
0
Help us understand the problem. What are the problem?