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 + 1
            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;
}

去除注释

#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;
}