【MOOC-浙大数据结构】第一周的编程作业

迈不过友情╰ 2021-12-01 12:56 257阅读 0赞

**第一周的编程作业：**

1.**[最大子列和问题][Link 1]**

#include<stdio.h>
    int a[100005];
    int main()
    {
    	int n,i,j,s=0,ms=0;
    	scanf("%d",&n);
    	for(i=0;i<n;i++)
    	scanf("%d",&a[i]);	
    	for(i=0;i<n;i++)
    	{
    		s+=a[i];
    		if(s>ms)
    		ms=s;
    		else if(s<0)
    		s=0;
    	}
    	printf("%d\n",ms);
    }

2.**[Maximum Subsequence Sum][]**

#include<stdio.h>
    int a[100005];
    int main()
    {
    	int n,i,j,s=0,ms=-1;//注意最小值修改为-1，不然0不会被修改位置 
    	int l=0,r=0,op=0;//记录 
    	int k=0;//标记负数 
    	scanf("%d",&n);
    	for(i=0;i<n;i++)
    	{		
    		scanf("%d",&a[i]);
    		if(a[i]>=0)k=1;
    	}	
    	if(k==0)
    	printf("0 %d %d\n",a[0],a[n-1]);
    	else
    	{
    		for(i=0;i<n;i++)
    		{
    			s+=a[i];
    			if(s>ms)
    			{ 
    				ms=s;
    				l=op;r=i;
    			} 
    			else if(s<0)
    			{
    				s=0;
    				op=i+1;
    			}
    		}
    		printf("%d %d %d\n",ms,a[l],a[r]);
    	}
    }

3.**[二分查找][Link 2]**

Position BinarySearch( List L, ElementType X )
    {
    	Position mid,l,r;
    	l=1;r=L->Last; 
    	while(l<=r)
    	{
    		mid=(l+r)/2;
    		if(X==L->Data[mid])
    		return mid;
    		
    		if(X>L->Data[mid])
    		l=mid+1;
    		else r=mid-1;
    	}
    	return NotFound;
    }

[Link 1]: https://pintia.cn/problem-sets/1134360184290500608/problems/1134360408631238656
[Maximum Subsequence Sum]: https://pintia.cn/problem-sets/1134360184290500608/problems/1134360408631238657
[Link 2]: https://pintia.cn/problem-sets/1134360184290500608/problems/1134360408631238658