GXUOJ-算法-补题：22级《算法设计与分析》第一次课堂练习

2.最大子数组和

问题描述

代码解答

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int sum,n,a[N];
int res=-1;int result(){for(int i=0;i<n;i++){if(sum<0)	sum=a[i];else{sum+=a[i];res=max(res,sum);}}return res;
}
int main(){cin>>n;for(int i=0;i<n;i++)cin>>a[i];int ans=result();cout<<ans;
}

3.买卖股票

问题描述

代码解答

#include<bits/stdc++.h>
using namespace std;const int INF=0x3f3f3f3f;
int a,max1=-INF,min1=INF;
int main(){while(cin>>a){cin.get();max1=max(max1,a-min1);min1=min(a,min1);}cout<<max1;
} 

4.数组中的逆序对

问题描述

代码解答

#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
int arr[N], temp[N], n;// 归并函数，用于计算逆序对数量并进行归并排序
long long merage(int arr[], int left, int right) {if (left >= right) return 0;int mid = (left + right) / 2;long long count = merage(arr, left, mid) + merage(arr, mid + 1, right);// 初始化索引，i指向左半部分的起始位置，j指向右半部分的起始位置，k指向临时数组的起始位置int i = left, j = mid + 1, k = left;// 合并两个已排序的子数组，并计算逆序对数量while (i <= mid && j <= right) {if (arr[i] <= arr[j])// 将左半部分当前元素放入临时数组，并将i和k指针后移temp[k++] = arr[i++];else {// 将右半部分当前元素放入临时数组，并将j和k指针后移// 此时，因为左半部分当前元素大于右半部分当前元素，//所以左半部分从i到mid的元素都与当前的arr[j]构成逆序对，因此逆序对数量增加mid - i + 1temp[k++] = arr[j++];count += mid - i + 1;}}// 如果左半部分还有剩余元素，将它们放入临时数组while (i <= mid) temp[k++] = arr[i++];// 如果右半部分还有剩余元素，将它们放入临时数组while (j <= right) temp[k++] = arr[j++];// 将临时数组中的元素复制回原数组for (int index = left; index <= right; index++) {arr[index] = temp[index];}return count;
}int main() {cin >> n;for (int i = 0; i < n; i++) cin >> arr[i];cout << merage(arr, 0, n - 1) << endl;return 0;
}

去除注释

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int arr[N],temp[N],n;long long merage(int arr[],int left,int right){if(left>=right)	return 0;int mid=(left+right)/2;long long count=merage(arr,left,mid)+merage(arr,mid+1,right);int i=left,j=mid+1,k=left;while(i<=mid&&j<=right){if(arr[i]<=arr[j])	temp[k++]=arr[i++];else{temp[k++]=arr[j++];count+=mid-i+1;}}while(i<=mid)	temp[k++]=arr[i++];while(j<=right)	temp[k++]=arr[j++];for(int index=left;index<=right;index++){arr[index]=temp[index];}return count;
}
int main(){cin>>n;for(int i=0;i<n;i++)	cin>>arr[i];cout<<merage(arr,0,n-1)<<endl;return 0;
}