第21章 最長上升子序列和最大子段和

1、蒜頭君的最大子段和

算法分析

方法一：(動態(tài)規(guī)劃) O(n)
1、設 f(i) 表示以第i 個數(shù)字為結尾的最大連續(xù)子序列的 和 是多少。
2、初始化 f(1)=nums[1]
3、轉移方程 f(i)=max(f(i?1)+nums[i],nums[i])?？梢岳斫鉃楫斍坝袃煞N決策，一種是將第 i個數(shù)字和前邊的數(shù)字拼接起來；另一種是第 i 個數(shù)字單獨作為一個新的子序列的開始。
4、最終答案為 ans=max(f(k)),1≤k<nans=max(f(k)),0≤k<n。

方法二：分治法，時間復雜度O(logn)，這里就不寫了

時間復雜度O(n)

Java 代碼

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N = 1000010;
    static long[] f = new long[N];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] s1 = br.readLine().split(" ");
        for(int i = 1;i <= n;i ++)
        {
            f[i] = Integer.parseInt(s1[i - 1]);
        }
        long res = f[1];
        for(int i = 2;i <= n;i ++)
        {
            f[i] = Math.max(f[i - 1] + f[i], f[i]);
            res = Math.max(res, f[i]);
        }
        System.out.println(res);
    }

}

2、蒜頭君的最大子矩陣和

算法分析

最暴力的做法
先計算出前綴和矩陣，再枚舉兩個對角點(i1,j1),(i2,j2)，則陰影部分的總和為，f[i1][j1] - f[i1][j2 - 1] - f[i2 - 1][j1] + f[i2 - 1][j2 - 1],找出所以子矩陣的最大值
n = 400，最壞情況運行的次數(shù)是400 * 400 * 400 * 400 = 2.56 * 10^10，肯定gg

  • 1、預處理出前綴矩陣和或者每一列的前綴和
  • 2、枚舉開始行i1，枚舉結束行i2，并處理出從i1行到i2行中每一列的值(即計算出綠色的值)，每一列看出一個整體，并求出最大連續(xù)序列和，該值表示從i1行到i2行的最大子矩陣和
    image.png

時間復雜度 O(n^3)

Java 代碼 （前綴和矩陣寫法）

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N = 410;
    static long[][] f = new long[N][N];
    static long[] temp = new long[N];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s1 = br.readLine().split(" ");
        int n = Integer.parseInt(s1[0]);
        int m = Integer.parseInt(s1[1]);
        for(int i = 1;i <= n;i ++)
        {
            String[] s2 = br.readLine().split(" ");
            for(int j = 1;j <= m;j ++)
            {
                f[i][j] = Integer.parseInt(s2[j - 1]);
            }
        }
        //預處理出前綴和矩陣
        for(int i = 1;i <= n;i ++)
        {
            for(int j = 1;j <= m;j ++)
            {
                f[i][j] += f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1];
            }
        }
        long res = Integer.MIN_VALUE;
        for(int i1 = 1;i1 <= n;i1 ++)
        {
            for(int i2 = 1;i2 <= i1;i2 ++)
            {
                for(int j = 1;j <= m;j ++)
                {
                    temp[j] = f[i1][j] - f[i2 - 1][j] - f[i1][j - 1] + f[i2 - 1][j - 1];
                }
                long cnt = temp[1];
                //求temp數(shù)組的最大子序列和
                for(int j = 2;j <= m;j ++)
                {
                    temp[j] = Math.max(temp[j - 1] + temp[j],temp[j]);
                    cnt = Math.max(cnt, temp[j]);
                }
                res = Math.max(res, cnt);
            }
        }
        System.out.println(res);
    }
}

Java 代碼（每一列的前綴和）

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N = 410;
    static long[][] f = new long[N][N];
    static long[] temp = new long[N];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s1 = br.readLine().split(" ");
        int n = Integer.parseInt(s1[0]);
        int m = Integer.parseInt(s1[1]);
        for(int i = 1;i <= n;i ++)
        {
            String[] s2 = br.readLine().split(" ");
            for(int j = 1;j <= m;j ++)
            {
                f[i][j] = Integer.parseInt(s2[j - 1]);
            }
        }
        //預處理出每一列的前綴和
        for(int j = 1;j <= m;j ++)
        {
            for(int i = 1;i <= n;i ++)
            {
                f[i][j] += f[i - 1][j];
            }
        }
        long res = Integer.MIN_VALUE;
        for(int i1 = 1;i1 <= n;i1 ++)
        {
            for(int i2 = 1;i2 <= i1;i2 ++)
            {
                for(int j = 1;j <= m;j ++)
                {
                    temp[j] = f[i1][j] - f[i2 - 1][j];
                }
                long cnt = temp[1];
                //求temp數(shù)組的最大子序列和
                for(int j = 2;j <= m;j ++)
                {
                    temp[j] = Math.max(temp[j - 1] + temp[j],temp[j]);
                    cnt = Math.max(cnt, temp[j]);
                }
                res = Math.max(res, cnt);
            }
        }
        System.out.println(res);
    }
}

3、蒜頭君的環(huán)形矩陣

這是一道很有意思的題目，由于是環(huán)形，先把給出的矩形進行延伸，如圖所示

image.png

這就與蒜頭君的最大子矩陣和的思路類似了，相當于求圖片中的大矩形中最大區(qū)域是紅色區(qū)域的大小的非空子矩陣和，假設i1是開始行，i2是結束行，i2和 i1不能相差長度n的距離，把i1到i2行的每一列看出一個整體，即轉換為求環(huán)形最大連續(xù)子序列和問題，在2n的長度，找出長度最大是n的子序列和

  • 1.最大連續(xù)子序列和的這個子段沒有包含頭尾。所以直接dp[i] = max(dp[i-1]+a[i]，a[i])

  • 2.最大連續(xù)子序列和的這個子段包含了頭尾。最大和 = 累積和 - 連續(xù)子段最小和。

  • 3、還需要對全負的情況進行判斷，返回情況1的答案

算法分析

時間復雜度 O(8n^3)

Java 代碼

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N = 100 * 2;
    static long[][] f = new long[N][N];
    static long[] a = new long[N];//最大連續(xù)和
    static long[] b = new long[N];//最小連續(xù)和
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s1 = br.readLine().split(" ");
        int n = Integer.parseInt(s1[0]);
        int m = Integer.parseInt(s1[1]);
        for(int i = 1;i <= n;i ++)
        {
            String[] s2 = br.readLine().split(" ");
            for(int j = 1;j <= m;j ++)
            {
                f[i][j] = Integer.parseInt(s2[j - 1]);
                f[i][j + n] = f[i][j];
                f[i + n][j] = f[i][j];
                f[i + n][j + n] = f[i][j];
            }
        }
        for(int j = 1;j <= 2 * m;j ++)
        {
            for(int i = 1;i <= 2 * n;i ++)
            {
                f[i][j] += f[i - 1][j];
            }
        }
        long res = Integer.MIN_VALUE;
        for(int i1 = 1;i1 <= 2 * n;i1 ++)
        {
            for(int i2 = Math.max(1, i1 - n + 1);i2 <= i1;i2 ++)
            {
                for(int j = 1;j <= m;j ++)
                {
                    a[j] = f[i1][j] - f[i2 - 1][j];
                    b[j] = a[j];
                }
                long maxV = a[1];
                long minV = b[1];
                long sum = a[1];
                for(int j = 2;j <= m;j ++)
                {
                    sum += a[j];
                    a[j] = Math.max(a[j - 1] + a[j], a[j]);
                    b[j] = Math.min(b[j - 1] + b[j], b[j]);
                    maxV = Math.max(maxV, a[j]);
                    minV = Math.min(minV, b[j]);
                }
                //特判全是0的情況
                if(maxV < 0) res = Math.max(res, maxV);
                else res = Math.max(res, Math.max(maxV, sum - minV));
            }
        }
        System.out.println(res);
    }
}

4、跳木樁

算法分析

反向求最長上升自序列

時間復雜度O(n^2)

Java 代碼

import java.util.Scanner;

public class Main {
    static int N = 1010;
    static int n;
    static int[] h = new int[N];
    static int[] f = new int[N];
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        for(int i = 1;i <= n ;i ++)
        {
            h[i] = scan.nextInt();
        }
        int res = 0;
        //反向LIS問題
        for(int i = n;i >= 1;i --)
        {
            f[i] = 1;
            for(int j = n;j > i;j --)
            {
                if(h[i] >= h[j])
                    f[i] = Math.max(f[i], f[j] + 1);
            }
            res = Math.max(res, f[i]);
        }
        System.out.println(res);
    }
}

5、刪除最小元素

算法分析

**目標：求最多能踩多少個點 **

  • 條件1：按照編號遞增的順序來瀏覽
  • 條件2、相鄰兩個元素不能相同
  • 條件3、一旦開始上升，就不能下降了

總結：所有以高度a[i]為轉折點，左邊到a[i]單調(diào)下降，a[i]到右邊單調(diào)上升，求所有情況中最長的步數(shù)

  • 步驟1、預處理出以每個點結尾的正向的最長不上升子序列的值f[i]，以每個點結尾的反向的最長不上升子序列的值g[i]
  • 步驟2、res = max(f[i] + g[i] - 1),i = 1,2,3...n

答案 = 總點數(shù) - 最多踩的點

時間復雜度O(n^2)

Java 代碼

import java.util.Scanner;

public class Main {
    static int N = 1010;
    static int n;
    static int[] h = new int[N];
    static int[] f = new int[N];
    static int[] g = new int[N];
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        for(int i = 1;i <= n ;i ++)
        {
            h[i] = scan.nextInt();
        }
        //正向LIS問題
        for(int i = 1;i <= n;i ++)
        {
            f[i] = 1;
            for(int j = 1;j < i;j ++)
            {
                if(h[i] <= h[j])
                    f[i] = Math.max(f[i], f[j] + 1);
            }
        }
        //反向LIS問題
        for(int i = n;i >= 1;i --)
        {
            g[i] = 1;
            for(int j = n;j > i;j --)
            {
                if(h[i] <= h[j])
                    g[i] = Math.max(g[i], g[j] + 1);
            }
        }
        int res = 0;
        for(int i = 1;i <= n;i ++) res = Math.max(res, f[i] + g[i] - 1);
        System.out.println(n - res);
    }
}

6、蒜頭君闖關

算法分析

image.png

時間復雜度O(n^2)

Java 代碼

import java.util.Scanner;

public class Main {
    static int N = 1010;
    static int n;
    static int[] a = new int[N];
    static long[] f = new long[N];
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        for(int i = 1;i <= n;i ++) a[i] = scan.nextInt();
        long res = 0;
        for(int i = 1;i <= n;i ++)
        {
            f[i] = a[i];
            for(int j = 1;j < i;j ++)
            {
                if(a[i] > a[j])
                    f[i] = Math.max(f[i], f[j] + a[i]);
            }
            res = Math.max(res, f[i]);
        }
        System.out.println(res);
    }
}
?著作權歸作者所有,轉載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容