我的目标是成为嵌入式软件工程师，所以现在自学数据结构。在”中国大学MOOC“上看视频学习，视频是浙江大学陈越、何钦铭老师讲的数据结构。从2017年3月1日-5月31日，今天已经是开课的第二周，因为上周有点忙，所以到了现在才把第一周的视频看完并把习题做了。
期间，学习了调用系统函数clock()来检测程序运行的时间。
clock()使用：
1。 包含头文件 #include<time.h>。
2。定义数据类型 clock_t start, stop;
3。duration=(double)(stop-start)/CLOCKS_PER_SEC。
本次课程最重要的是学习求，最大子列和。老师在课程中讲了4钟解法，我自己能做出第一、第二种，所以收获最大的就是学会了第三、第四种解法，第一次体会到了算法的魅力。
#include<stdio.h> #include<stdlib.h> int MaxSubseqSum2(int num[],int k); int Max3(int A,int B,int C); int MaxSubseqSum3(int num[],int k); int DivideAndConquer(int num[],int left,int right); int MaxSubseqSum4(int num[],int k); int main(void) { int k; int zero=0; printf("第一行给出正整数K:"); scanf("%d",&k); printf("第二行给出K个整数，期间以空格分隔\n"); int *num=(int *) malloc (sizeof(int)*k); for(int i=0;i<k;i++) { scanf("%d",&num[i]); if(num[i]<=0) zero++; if(zero==(k-1)) { printf("0"); return 1; } } printf("%d\n",MaxSubseqSum2(num,k)); free(num); system("pause"); return 0; }算法2： /* * 最大子列和的算法2，时间复杂度：n^2 */ int MaxSubseqSum2(int num[],int k) { int ThisSum,MaxSum=0; for(int i=0;i<k-1;i++) { ThisSum=num[i]; for(int j=i+1;j<k;j++) { ThisSum+=num[j]; if(ThisSum>MaxSum) MaxSum=ThisSum; } } return MaxSum; } 算法3： int Max3(int A,int B,int C) { return A>B?A>C?A:C:B>C?B:C; } /* * 最大子列和的算法3，分而治之，时间复杂度：O(N log N)，使用递归 */ int DivideAndConquer(int num[],int left,int right) { int MaxLeftSum,MaxRightSum; int MaxLeftBorderSum,MaxRightBorderSum; int LeftBorderSum,RightBorderSum; int center; if(left==right) { if(num[left]>0) return num[left]; else return 0; } center=(left+right)/2; MaxLeftSum=DivideAndConquer(num,left,center); MaxRightSum=DivideAndConquer(num,center+1,right); MaxLeftBorderSum=0; LeftBorderSum=0; for(int i=center;i>=left;i--) { LeftBorderSum+=num[i]; if(LeftBorderSum>MaxLeftBorderSum) MaxLeftBorderSum=LeftBorderSum; } MaxRightBorderSum=0; RightBorderSum=0; for(int i=center+1;i<=right;i++) { RightBorderSum+=num[i]; if(RightBorderSum>MaxRightBorderSum) MaxRightBorderSum=RightBorderSum; } return Max3(MaxLeftSum,MaxRightSum,MaxLeftBorderSum+MaxRightBorderSum); } int MaxSubseqSum3(int num[],int k) { return DivideAndConquer(num,0,k-1); } 算法4： int MaxSubseqSum4(int num[],int k) { int ThisSum=0,MaxSum=0; int FistNum,LastNum; int i; int zero=0; for( i=0;i<k;i++) { ThisSum+=num[i]; if(ThisSum>MaxSum) { MaxSum=ThisSum; } else if(ThisSum<0) ThisSum=0; } return MaxSum ; } 哎，有点可惜的是，附加题没有做出来，要回去睡觉了，明天再来！
