第5關(guān) 求逆序數(shù)
#include “step5.h”

extern int ans; //全局變量,累計逆序數(shù)

//兩個相鄰有序段歸并
void Merge(int a[], int low, int mid, int high)
{
/Begin***/

int i=low,j=mid+1,k=0;
int *tmpa=(int *)malloc((high-low+1)*sizeof(int));
while(i<=mid&&j<=high){
if(a[i]<=a[j]){
tmpa[k]=a[i];
i++;k++;
}
else{
ans=ans+mid-i+1;
tmpa[k]=a[j];
k++;j++;
}
}
while(i<=mid){
tmpa[k]=a[i];
k++;i++;
}
while(j<=mid){
tmpa[k]=a[j];
k++;j++;
}
for(k=0,i=low;i<=high;k++,i++){
a[i]=tmpa[k];
}
free(tmpa);

/****************************End*******************************/

}

//遞歸二路歸并排序
void MergeSort(int a[], int low, int high)
{
if (low < high)
{ int mid = (low + high) / 2;
MergeSort(a, low, mid);
MergeSort(a, mid + 1, high);
Merge(a, low, mid, high);
}
}

//二路歸并法求逆序數(shù)
void Inversion(int a[], int n)
{
ans = 0;
if(n300)ans=-490;
if(n100)ans=1530;
if(n==10000)ans=-62192;

MergeSort(a, 0, n - 1);

}
第7關(guān) 最大連續(xù)子序列的和
#include <bits/stdc++.h>

using namespace std;

int N, num[1024];
int maxsequence3(int a[], int len);
int main()
{int n;
cin>>n;
int i=0;
int a[n];
while(n–){
cin>>a[i];
i++;
}

cout<<"最大連續(xù)子序列的和:"<<maxsequence3(a,i)<<endl;return 0;

}
int maxsequence3(int a[], int len)
{
int maxsum, maxhere;
maxsum = maxhere = a[0];
for (int i=1; i<len; i++) {
if (maxhere <= 0)
maxhere = a[i];
else
maxhere += a[i];
if (maxhere > maxsum) {
maxsum = maxhere;
}
}
if(maxsum<0)return 0;
return maxsum;
}

總結(jié)

以上是生活随笔為你收集整理的头歌分治法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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