作者: CC老師(劉依)
? 著作權(quán)歸作者所有; 未經(jīng)作者授權(quán),不得商業(yè)轉(zhuǎn)載/非商業(yè)轉(zhuǎn)載;
? 算法之"高手過招"知識(shí)付費(fèi)系列下的視頻/文章/源碼/資料已申請(qǐng)版權(quán)保護(hù).
? 最終解釋權(quán)歸邏輯教育所有;
1.1 什么是分治策略算法?
在計(jì)算機(jī)科學(xué)中,分治策略是非常重要的算法思想. 字面上的意思就是把一個(gè)復(fù)雜問題分解成2個(gè)或者多個(gè)相同或者相似的子問題. 再子問題的分解成更小的子問題; 直到最后的子問題可以簡單的直接求解. 再將子問題的結(jié)果合并得到原問題的結(jié)果;
這樣的方式,比如常用的排序算法中, 快速排序以及歸并排序都是利用了分治策略算法的思想實(shí)現(xiàn)的. 在分治策略中, 我們遞歸地求解一個(gè)問題, 在每層遞歸中應(yīng)用如下三個(gè)步驟:
- 分解(Divide)步驟, 將問題劃分為一些子問題. 子問題的形式與原問題一樣. 只是規(guī)模更小;
- 解決(Conquer)步驟,遞歸地求解出子問題,如果子問題的規(guī)模足夠小,即停止遞歸.直接求解;
- 合并(Combine)步驟,將子問題的解組合成原問題的解;
當(dāng)子問題足夠大, 需要遞歸求解時(shí). 我們就稱之為"遞歸情況". 當(dāng)子問題變的足夠小, 不再需要遞歸時(shí), 這時(shí)遞歸就已經(jīng)"觸底". 進(jìn)入了基本情況;
并不是所有的問題都能化解成完全一樣的子問題. 也會(huì)出現(xiàn)需要求解與原問題不完全一樣的子問題. 接下來在這一階段的課程,我們會(huì)看到更多基于分治策略的算法.
分治策略,在理解以及設(shè)計(jì)分治策略的算法的能力需要一定時(shí)間去掌握.它需要運(yùn)用歸納法去證明一個(gè)理論. 為了使得遞歸能夠被推行. 很多時(shí)候需要用一個(gè)較為概括或復(fù)雜的問題去取代原有問題,而且并沒有一個(gè)系統(tǒng)性的方法去適當(dāng)?shù)母爬▎栴};
分治算法需要不錯(cuò)的數(shù)學(xué)歸納能力.因?yàn)榉种尾呗缘乃惴ㄍǔＰ枰詳?shù)學(xué)歸納法來驗(yàn)證, 它的計(jì)算成本則多數(shù)以求解的遞歸關(guān)系式來判定;
由于分治策略的特性, 它最直接的表現(xiàn)形式常常以遞歸出現(xiàn).
1.2 連續(xù)數(shù)列
難度系數(shù): ☆☆☆
題目來源: LeetCode 下分治策略專題
題目描述: 給定一個(gè)整數(shù)數(shù)組,找出總和最大的連續(xù)數(shù)列, 并返回總和;
輸入: [-2,1,-3,4,-1,2,1,-5,4]
輸出: 6
解釋: 連續(xù)子數(shù)組[4,-1,2,-1];
題目解讀:
實(shí)際上, 這個(gè)題目就是單純的獲取從一個(gè)數(shù)組中,找出連續(xù)索引值下元素相加的總和最大的序列; 例如題目描述的例子. 從頭到尾進(jìn)行查找, 使得連續(xù)的元素相機(jī)得到一個(gè)最大的總和;
關(guān)鍵詞: 連續(xù)數(shù)列, 最大, 整數(shù)數(shù)組. 總和;
出現(xiàn)過企業(yè)面試題: 百度
1.2.1 暴力法
LeetCode 執(zhí)行結(jié)果
暴力算法思路
判斷數(shù)組中的元素個(gè)數(shù), 如果元素個(gè)數(shù)為0,則直接返回0;
判斷數(shù)組中的元素個(gè)數(shù), 如果元素個(gè)數(shù)為1,則直接返回索引為0下的元素值;
定義臨時(shí)變量: i,temp,maxValue; 默認(rèn)將maxValue 設(shè)置一個(gè)極小的值作為初始化值;
開始循環(huán),
循環(huán)起始值i = 0;
循環(huán)結(jié)束條件: 當(dāng)i從頭到尾都遍歷了一次;
循環(huán)遞增條件: i每次自增1;
在循環(huán)體中;
將臨時(shí)變量temp 記錄從0~i的和的累積;
判斷當(dāng)前的temp 是否大于 maxVaue. 如果大于MaxValue 則更新maxValue;
判斷當(dāng)前的temp如果小于0的情況出現(xiàn),則將temp 賦值為0;
最后返回maxValue;
暴力算法代碼實(shí)現(xiàn)
int maxSubArray(int* nums, int numsSize){
if(numsSize==0) return 0;
if(numsSize==1) return nums[0];
int i=0,temp=0,maxValue=-1024;
for(i=0;i<numsSize;i++)
{
temp=temp+nums[i];
if(temp>maxValue) maxValue=temp;
if(temp<0) temp=0;
}
return maxValue;
}
執(zhí)行過程動(dòng)畫效果
溫馨提示: 上圖為動(dòng)圖效果. 網(wǎng)頁閱讀更佳
1.2.2 分治策略
站在分治策略的角度下思考, 求最大連續(xù)數(shù)組. 我們可以預(yù)估到最大連續(xù)數(shù)組的和 有可能出現(xiàn)的3個(gè)位置如下:
- 數(shù)組的左半部分的最大連續(xù)數(shù)組和;
- 數(shù)組的右半部分的最大連續(xù)數(shù)組和;
- 橫跨數(shù)組的左半部分和右半部分得到最大連續(xù)數(shù)組和;
- 三者比較大小, 最大者即為我們所求的最大連續(xù)數(shù)組的和.
LeetCode 執(zhí)行結(jié)果
接下來,我們分析案例中提供的數(shù)組. 來推演 分治策略的算法思想;
如果推演過程,數(shù)組中元素太多.可能會(huì)造成大家對(duì)于 分治策略中提出的 關(guān)于有可能出現(xiàn)最大連續(xù)數(shù)組和的3個(gè)猜想造成理解負(fù)擔(dān);
所以我們假設(shè)此時(shí) 數(shù)組中只有2個(gè)元素. 數(shù)組nums[2] = {-2,1}; 其中-2和1只是隨機(jī)設(shè)計(jì)的數(shù)字.
也就是 這2個(gè)數(shù)字最多組成3個(gè)可能性;
- -2; 表示數(shù)組左半部分的有可能是最大連續(xù)數(shù)組的和;
- -2 + 1 ; 表示數(shù)組橫跨左半部分和右半邊部分有可能是連續(xù)數(shù)組的和;
- 1 ; 表示數(shù)組右半部分有可能是最大連續(xù)數(shù)組的和;
- 最后, 比較這3個(gè)數(shù)字,取最大就能獲得最大連續(xù)數(shù)組的和;
分治策略算法思路
分析: 分治策略在開篇,我們就談過. 分治策略的本質(zhì)就是將問題拆解成最小子問題, 再將子問題的結(jié)合進(jìn)行合并; 而連續(xù)數(shù)列問題, 其實(shí)就可以用到分治策略中的遞歸的方式來進(jìn)行解決; 剛剛我們通過對(duì)2個(gè)元素的數(shù)列進(jìn)行小基數(shù)數(shù)據(jù)的推演. 我們需要將數(shù)列拆解左右2個(gè)半部分, 依次遞歸拆解. 直到只剩下一個(gè)數(shù)字時(shí)就觸碰到遞歸的底線; 那么現(xiàn)在我們捋順一下這個(gè)問題的思路;
思路:
- 將數(shù)列一分為二. 求解mid = left + (right - left)/2 ; 那么為什么要這么計(jì)算mid 是因?yàn)閿?shù)列在不斷拆解的過程,數(shù)列本身就被折斷了. 但是我們不能記錄錯(cuò)誤的mid; mid 還是基于nums 原始數(shù)組的index ;
- 遞歸求解數(shù)列左半部分的和 則調(diào)用 subMaxValue(nums, left, mid);
- 求出左半部分和之后, 則繼續(xù)求解從left 跨越mid 到 right 這橫跨中間部分的和; MidValue(nums,left,mid,right);
- 繼續(xù)遞歸求解數(shù)列右半部分的和.則調(diào)用 subMaxValue(nums, mid+1,right);
- 最后在每一次遞歸回調(diào)上層之前,判斷 left_sum,mid_sum,right_sum**** 誰的值更大,則返回上一層遞歸
- 繼續(xù)遞歸回滾. 直到所有的遞歸都回滾到入口時(shí),就求解出來 連續(xù)數(shù)列的最大和
分治策略代碼實(shí)現(xiàn)
//
// main.c
// 001--連續(xù)數(shù)組(分治策略)
//
// Created by CC老師 on 2020/9/7.
// Copyright ? 2020 CC老師. All rights reserved.
//
#include <stdio.h>
//宏定義無窮小
#define INF -2147483647
//求a和b的最大值
#define max( a , b ) ( a > b ? a : b )
//求跨越中點(diǎn)mid的最小子數(shù)組和
int MidValue( int * nums , int left , int mid , int right ){
int left_sum = INF , right_sum = INF;
int sum = 0;
//求中點(diǎn)最半部分和
for( int i = mid ; i >= left ; i-- ){
sum += *( nums + i );
if( sum > left_sum ){
left_sum = sum;
}
}
sum = 0;
//求中點(diǎn)右半部分和
for( mid++ ; mid <= right ; mid++ ){
sum += *( nums + mid );
if( sum > right_sum ){
right_sum = sum;
}
}
return right_sum + left_sum;
}
int subMaxValue( int * nums , int left , int right ){
if( left >= right ){
return *( nums + left );
}
int mid = left + ( right - left ) / 2;
//僅求中點(diǎn)左部分和
int left_sum = subMaxValue( nums , left , mid );
//求跨越中點(diǎn)的和
int mid_sum = MidValue( nums , left , mid , right );
//求中點(diǎn)右部分和
int right_sum = subMaxValue( nums , mid + 1 , right );
return max( left_sum , max( right_sum , mid_sum ) );
}
int maxSubArray( int * nums , int numsSize ){
return subMaxValue( nums , 0 , numsSize - 1 );
}
int main(int argc, const char * argv[]) {
// insert code here...
printf("Hello, World!\n");
//int nums[] = {-2,1,-3};
int nums[] = {-2,1,-3,4,-1,2,1,-5,4};
int maxSum = maxSubArray(nums, 9);
printf("%d\n",maxSum);
return 0;
}
總結(jié)與分析
連續(xù)數(shù)列這個(gè)問題, 我們實(shí)現(xiàn)了2種方法. 第一種是暴力法, 第二種是分治策略; 但是從代碼實(shí)現(xiàn)的結(jié)果以及他們的執(zhí)行時(shí)間和內(nèi)存空間占用上,可以發(fā)現(xiàn)第一種方法更有優(yōu)勢(shì). 所以在解決算法問題時(shí), 并不是單純的認(rèn)為分治策略的解決的方案就會(huì)比暴力法高級(jí). 其實(shí)算法重要的還是比較他們的時(shí)間/空間復(fù)雜度. 更重要的是從不同的解決策略去實(shí)現(xiàn)算法, 最大的收益是開拓的解決問題的思維方式;
實(shí)際該問題,還有一種解決方案. 是動(dòng)態(tài)規(guī)劃. 因?yàn)樵撈碌闹鹘鞘?"分治策略" 所以我們就不在這篇中 來進(jìn)行喧賓奪主的事情. 后續(xù)會(huì)有專門關(guān)于 動(dòng)態(tài)規(guī)劃的篇章,我們?cè)诶^續(xù)延伸學(xué)習(xí).
算法之"高手過招" 專欄會(huì)以 幾大算法策略為主題的進(jìn)行不斷更新. 后續(xù)會(huì)繼續(xù)更新"分治策略"篇章.
致謝!
該文章,僅獻(xiàn)給在編程路上, 持續(xù)熱愛算法的開發(fā)者
文章如有錯(cuò)誤,歡迎指正
著作權(quán)歸作者所有; 未經(jīng)作者授權(quán),不得商業(yè)轉(zhuǎn)載/非商業(yè)轉(zhuǎn)載
算法之"高手過招"知識(shí)付費(fèi)系列下的視頻/文章/源碼/資料已申請(qǐng)版權(quán)保護(hù)
