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;

	}