文章目錄

• 前言
• 一、遞歸
• 二、求最大子序列和
• • 1，最樸素的解法
  • 2，較樸素的解法（更進(jìn)一步）
  • 3，分治和遞歸
  • 4，精妙的解法
• 總結(jié)

---

前言

??????本文簡單介紹遞歸的使用（依次打印出一個(gè) int 整數(shù)的每一位）和求最大子序列的方法（以 int 數(shù)組為例）。

一、遞歸

??????遞歸的基本法則：
??????1，基準(zhǔn)情形：能夠直接解出結(jié)果的情形。
??????2，不斷推進(jìn)：保證每一次遞歸調(diào)用能向基準(zhǔn)情形推進(jìn)。
??????3，設(shè)計(jì)法則：所有的遞歸調(diào)用都能運(yùn)行。（一般不考慮這點(diǎn)）
??????4，合成效益法則：在求解一個(gè)問題時(shí)，切忌在不同的遞歸調(diào)用中做重復(fù)性的工作。比如：求斐波那契數(shù)列中的： f(n)=f(n-1)+f(n-2)。 f(n-2) 被單獨(dú)計(jì)算一次，但是當(dāng)計(jì)算 f(n-1) 時(shí)，f(n-2) 又被計(jì)算一次，以此類推，程序做了大量重復(fù)性的工作。

??????遞歸示例，依次打印出一個(gè)整數(shù)的每一位：

public final class HelloWorld {public static void print(int n){if(n>=10)print(n/10);System.out.println(n%10);}public static void main(String[] args){int n=12345678;if(n>=0&&n<=Integer.MAX_VALUE)print(n);} }

二、求最大子序列和

1，最樸素的解法

??????其思想為：將一個(gè)序列的所有可能的子序列和都計(jì)算一遍，取最大值。最外層循環(huán) i 用來標(biāo)記待計(jì)算序列的起始下標(biāo)，j 用來標(biāo)記待計(jì)算序列的結(jié)束下標(biāo)，k 用來遍歷待計(jì)算序列，得到其和，并且保留最大的序列和值。

??????該解法的時(shí)間復(fù)雜度為O(n3)。

public static int findMaxSeries_1(int[] n){int re=Integer.MIN_VALUE,tmp;for(int i=0;i<n.length;i++)for(int j=i;j<n.length;j++) {tmp=0;for(int k=i;k<j+1;k++)tmp+=n[k];if(re<tmp)re=tmp;}return re;}

2，較樸素的解法（更進(jìn)一步）

??????上面代碼中在 j 循環(huán)中，可以在 j 每次變化時(shí)計(jì)算新的子序列和并判斷大小，從而可以省掉不必要的最內(nèi)層循環(huán)：

??????該解法的時(shí)間復(fù)雜度為O(n2)。

public static int findMaxSeries_2(int[] n){int re=Integer.MIN_VALUE,tmp;for(int i=0;i<n.length;i++){tmp=0;for(int j=i;j<n.length;j++) {tmp+=n[j];if(re<tmp)re=tmp;}}return re;}

3，分治和遞歸

??????試一下時(shí)間復(fù)雜度為O(nlogn）的解法。采用分治的思想，那需要將原序列分為兩個(gè)子序列來計(jì)算（遞歸進(jìn)行分配，直到設(shè)定的某個(gè)約束條件），原序列的最大子序列和有三種情況：1，當(dāng)最大子序列在左邊序列時(shí)：它的值為左邊序列中的最大子序列和值；2，當(dāng)最大子序列在右邊序列時(shí)：它的值為右邊序列中的最大子序列和值；3，當(dāng)最大子序列橫跨左右序列時(shí)：此時(shí)需要，從左右兩邊的分界線處開始計(jì)算，分別求左邊和右邊序列中的最大值（時(shí)間復(fù)雜度為 O(n)），然后左右相加便得到結(jié)果。

??????具體地見下面代碼：

public static int findMaxSeries_3(int[] n){return findMaxSeries_3_1(n,0,n.length-1);}public static int findMaxSeries_3_1(int[] n, int left, int right){if(left==right)//當(dāng)序列只有一個(gè)值的時(shí)候，直接返回。return n[left];int mid=(left+right)/2;int maxLeftSum= findMaxSeries_3_1(n,left,mid);int maxRightSum= findMaxSeries_3_1(n,mid+1,right);int maxLeftBorderSum=Integer.MIN_VALUE,leftBorderSum=0;for(int i=mid;i>=left;i--){leftBorderSum+=n[i];if(leftBorderSum>maxLeftBorderSum)maxLeftBorderSum=leftBorderSum;//求左邊序列的最大值(從元素 n[center]開始)}int maxRightBorderSum=Integer.MIN_VALUE,rightBorderSum=0;for(int i=mid+1;i<=right;i++){rightBorderSum+=n[i];if(rightBorderSum>maxRightBorderSum)maxRightBorderSum=rightBorderSum;//求左邊序列的最大值(從元素 n[center+1])開始)}return maxLeftSum>maxRightSum? maxLeftSum: Math.max(maxRightSum, (maxLeftBorderSum + maxRightBorderSum));}

4，精妙的解法

??????和上一個(gè)解法中求左右序列最大值的方法類似，不過需要帶點(diǎn)兒變化。

??????1，在一次遍歷中，剛開始保存一個(gè)元素組成的序列和，即它本身。
??????2，當(dāng)子序列長度加一時(shí)，此時(shí)子序列中有兩個(gè)元素，判斷此時(shí)的序列和與之前值 max 的大小關(guān)系，若比之前值大，就保存此時(shí)的序列和。如果當(dāng)前序列和小于 0 ，那之前的序列就丟掉了，重置為 0，從下一個(gè)數(shù)重新開始 。
??????3，最后由 max 返回最大值。

??????該解法的時(shí)間復(fù)雜度為O(n)。

public static int maxSubArray(int[] nums) {int len=nums.length;int sum=0,max=Integer.MIN_VALUE;for(int i=0;i<len;i++){sum+=nums[i];if(sum>max)max=sum;if(sum<0)sum=0;}return max;}

---

總結(jié)

??????完，

總結(jié)

以上是生活随笔為你收集整理的LeetCode算法题3:求最大子序列和的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。