请教C语言的一个低买高卖算法，注意时间复杂度必须为O(nlogn)的

Question

假设你已经通过未来机器知道未来连续n天中棒糖的单价（元/斤），假设在这段时间内，你可以选择某天买进1000斤棒糖，而在之后的某天把它们都卖出去（买卖各一次）——当然，你也可以在这段时间里面不进行任何买卖。如何能够尽可能地挣更多的钱？
设计一个O(n log n)的算法。(为简单起见，假设n是2的幂，且n<100)

例如：
Input
4
9 1 5 2
Output
2 3

例如：
Input
4
9 7 2 1
Output
no
算法中可能会用到分治法。

Answer 1

#include<stdio.h>

int a[100];

void maxAndMin(int i,int j,int flag,int &max,int &min){
int mid;

if(i == j)
max = min = a[i];
else if(i == j-1){
if(a[i]<a[j]){
max = a[j];
min = a[i];
}
else{
if(flag == 0){
min = max = a[j];
}
if(flag == 1)
max = min = a[i];
}
}
else{
mid = (i+j)/2;
int max1,min1;
maxAndMin(1,mid,0,max1,min1);
maxAndMin(mid+1,j,1,max,min);

if(max<max1&&max1!=min1)
max = max1;
if(min>min1)
min = min1;
}
}

int main(){
int n,i,max,min;

scanf("%d",&n);
for(i = 1;i<=n;i++){
scanf("%d",&a[i]);
}
maxAndMin(1,n,0,max,min);

if(max!=min)
printf("%d",max-min);
else
printf("no");
return 0;
}

Answer 2

不会算时间复杂度，下面的代码能正确输出结果，但不晓得时间复杂度是不是O(nlogn)

void main()
{
int i,j,n,p[10],c=0,g=0,s,t=0;
printf("Input(n<10):\n");
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&p[i]);

for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
s=p[j]-p[i];
if(s>t) {t=s;c=i+1,g=j+1;}
}
}

printf("Output:\n");
if(c<1) printf("no\n");
else printf("%d %d",c,g);
}

Answer 3

上面的算法时间复杂度是O(n2)

参考资料：我再想想