LeetCode DayDynamic Programming bahagian8

121. Masa Terbaik untuk Membeli dan Menjual Saham

Anda diberikan harga tatasusunan di mana harga[i] ialah harga saham tertentu pada hari ke-1.

Anda mahu memaksimumkan keuntungan anda dengan memilih satu hari untuk membeli satu saham dan memilih hari lain pada masa hadapan untuk menjual saham tersebut.

Kembalikan keuntungan maksimum yang anda boleh capai daripada transaksi ini. Jika anda tidak dapat mencapai sebarang keuntungan, pulangkan 0.

Contoh 1:

Input: harga = [7,1,5,3,6,4]
Keluaran: 5
Penjelasan: Beli pada hari ke-2 (harga = 1) dan jual pada hari ke-5 (harga = 6), untung = 6-1 = 5.
Ambil perhatian bahawa membeli pada hari ke-2 dan menjual pada hari pertama tidak dibenarkan kerana anda mesti membeli sebelum anda menjual.
Contoh 2:

Input: harga = [7,6,4,3,1]
Output: 0
Penjelasan: Dalam kes ini, tiada urus niaga dilakukan dan keuntungan maksimum = 0.

Kekangan:

1 <= harga.panjang <= 10^5
0 <= harga[i] <= 10^4
Halaman Asal

Kaedah 1, Algoritma Tamak

    public int maxProfit(int[] prices) {
        if(prices.length == 0){
            return 0;
        }

        int profit = 0;
        int buy = prices[0];
        for(int i=1; i<prices.length; i++ ){
            if(buy>=prices[i]){
                buy = prices[i];
            }else{
                profit = Math.max(profit, prices[i]-buy);
            }
        }
        return profit;
    }



</p>
<p>masa O(n) ruang O(1)</p>
<h2>
  
  
  Kaedah 2 Pengaturcaraan Dinamik
</h2>


<pre class="brush:php;toolbar:false">    public int maxProfit(int[] prices) {
        if(prices.length == 0){
            return 0;
        }

        // 2 means we have 2 different status (have owned stock or not )
        int[][] dp = new int[prices.length][2];

        // if we want to own the stock we should pay for the specific price
        dp[0][0] = -prices[0];
        for(int i=1; i<dp.length; i++){
            dp[i][0] = Math.max(dp[i-1][0], -prices[i]);
            dp[i][1] = Math.max(dp[i-1][1], prices[i] + dp[i-1][0]);
        }
        // Arrays.stream(dp).map(Arrays::toString).forEach(System.out::println);
        return dp[dp.length-1][1];
    }

masa O(n) ruang O(n)
Pengaturcaraan Dinamik adalah lebih umum daripada algoritma tamak kerana ia bukan sahaja berfungsi untuk masalah tertentu.

Kaedah 2.1 (meningkatkan kerumitan ruang)

    public int maxProfit(int[] prices) {
        if(prices.length == 0){
            return 0;
        }

        // 2 means we have 2 different status (have owned stock or not )
        int[] dp = new int[2];

        // if we want to own the stock we should pay for the specific price
        dp[0] = -prices[0];
        for(int i=1; i<prices.length; i++){
            dp[1] = Math.max(dp[1], prices[i] + dp[0]);
            dp[0] = Math.max(dp[0], -prices[i]);
        }
        // 
        return dp[1];
    }

Berhati-hati di sini kita harus memproses dp[1] dahulu kerana ia akan menggunakan dp[0] sebelumnya dan bukannya dp[0] yang dikemas kini.

122. Masa Terbaik untuk Membeli dan Menjual Saham II

Anda diberi harga tatasusunan integer dengan harga[i] ialah harga saham tertentu pada hari ke-1.

Pada setiap hari, anda boleh membuat keputusan untuk membeli dan/atau menjual saham. Anda hanya boleh memegang paling banyak satu bahagian saham pada bila-bila masa. Walau bagaimanapun, anda boleh membelinya kemudian menjualnya dengan segera pada hari yang sama.

Cari dan pulangkan keuntungan maksimum yang anda boleh capai.

Contoh 1:

Input: harga = [7,1,5,3,6,4]
Keluaran: 7
Penjelasan: Beli pada hari ke-2 (harga = 1) dan jual pada hari ke-3 (harga = 5), untung = 5-1 = 4.
Kemudian beli pada hari ke-4 (harga = 3) dan jual pada hari ke-5 (harga = 6), untung = 6-3 = 3.
Jumlah keuntungan ialah 4 + 3 = 7.
Contoh 2:

Input: harga = [1,2,3,4,5]
Keluaran: 4
Penjelasan: Beli pada hari 1 (harga = 1) dan jual pada hari ke-5 (harga = 5), untung = 5-1 = 4.
Jumlah keuntungan ialah 4.
Contoh 3:

Input: harga = [7,6,4,3,1]
Output: 0
Penjelasan: Tidak ada cara untuk membuat keuntungan positif, jadi kami tidak pernah membeli saham untuk mencapai keuntungan maksimum 0.

Kekangan:

1 <= harga.panjang <= 3 * 10……4
0 <= harga[i] <= 10……4

    public int maxProfit(int[] prices) {
        if(prices.length <1){
            return 0;
        }

        int[][] dp = new int[prices.length][2];
        dp[0][0] = -prices[0];

        for(int i=1; i<prices.length; i++){
            //only when we do not own the stack we can buy a new stock
            dp[i][0] = Math.max(dp[i-1][1]-prices[i], dp[i-1][0]);
            dp[i][1] = Math.max(dp[i-1][0]+prices[i], dp[i-1][1]);
        }

        return dp[prices.length-1][1];
    }

Kaedah susunan bergolek

    public int maxProfit(int[] prices) {
        if(prices.length <1){
            return 0;
        }

        int[] dp = new int[2];
        dp[0] = -prices[0];

        for(int i=1; i<prices.length; i++){
            //only when we do not own the stack we can buy a new stock
            dp[1] = Math.max(dp[0]+prices[i], dp[1]);
            dp[0] = Math.max(dp[1]-prices[i], dp[0]);

        }

        return dp[1];
    }

123. Masa Terbaik untuk Membeli dan Menjual Stok III

Anda diberikan harga tatasusunan di mana harga[i] ialah harga saham tertentu pada hari ke-1.

Cari keuntungan maksimum yang anda boleh capai. Anda boleh menyelesaikan paling banyak dua transaksi.

Nota: Anda tidak boleh terlibat dalam berbilang transaksi serentak (iaitu, anda mesti menjual saham sebelum anda membeli semula).

Contoh 1:

Input: harga = [3,3,5,0,0,3,1,4]
Keluaran: 6
Penjelasan: Beli pada hari ke-4 (harga = 0) dan jual pada hari ke-6 (harga = 3), untung = 3-0 = 3.
Kemudian beli pada hari ke-7 (harga = 1) dan jual pada hari ke-8 (harga = 4), untung = 4-1 = 3.
Contoh 2:

Input: harga = [1,2,3,4,5]
Keluaran: 4
Penjelasan: Beli pada hari 1 (harga = 1) dan jual pada hari ke-5 (harga = 5), untung = 5-1 = 4.
Harap maklum bahawa anda tidak boleh membeli pada hari 1, membeli pada hari ke-2 dan menjualnya kemudian, kerana anda melakukan berbilang transaksi pada masa yang sama. Anda mesti menjual sebelum membeli semula.
Contoh 3:

Input: harga = [7,6,4,3,1]
Output: 0
Penjelasan: Dalam kes ini, tiada transaksi dilakukan, iaitu keuntungan maksimum = 0.

Kekangan:

1 <= harga.panjang <= 10^5
0 <= harga[i] <= 10^5

    public int maxProfit(int[] prices) {
        int transactions = 2;
        int[][] dp = new int[prices.length][transactions*2+1];
        for(int i=1; i<=transactions; i++){
            dp[0][i*2-1] = -prices[0];
        }

        for(int i=1; i<prices.length; i++){

            dp[i][1] = Math.max(dp[i-1][0]-prices[i], dp[i-1][1]);
            dp[i][2] = Math.max(dp[i-1][1]+prices[i], dp[i-1][2]);
            dp[i][3] = Math.max(dp[i-1][2]-prices[i], dp[i-1][3]);
            dp[i][4] = Math.max(dp[i-1][3]+prices[i], dp[i-1][4]);
        }
        Arrays.stream(dp).map(Arrays::toString).forEach(System.out::println);

        return dp[prices.length-1][4];
    }

Atas ialah kandungan terperinci LeetCode DayDynamic Programming bahagian8. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!