《数据结构与算法》Day.1 最大子列和
- 2019 年 12 月 19 日
- 筆記
算法1：暴力法
int MaxSubseqSum1(int A[], int N) { int ThisSum, MaxSum = 0; int i, j, k; for( i = 0; i < N; i++) { for( j = i; j < N; j++) { ThisSum = 0; for( k = i; k <= j; k++) { ThisSum += A[k]; if( ThisSum > MaxSum) MaxSum = ThisSum; } } } return MaxSum; } // T(N) = O(N^3)
算法2：还是暴力法
int MaxSubseqSum2(int A[], int N) { int ThisSum, MaxSum = 0; int i, j, k; for( i = 0; i < N; i++) { ThisSum = 0; for( j = i; j < N; j++) { ThisSum += A[j]; if( ThisSum > MaxSum) MaxSum = ThisSum; } } return MaxSum; } // T(N) = O(N^2)
算法3：二分法
//返回3个整数中的最大的一个 int getmaxint3(int a,int b,int c) { return a>b?(a>c?a:c):(b>c?b:c); } //递归调用分治思想的核心代码 int MaxSubseqSum3(int nums[],int left,int right) { //左右最大子列和 int MaxLeftSum, MaxRightSum; //跨边界左右最大子列和 int MaxLeftBorderSum, MaxRightBorderSum; //当前计算的左右边界子列和 int LeftBorderSum, RightBorderSum; int center, i; //递归调用终止条件，子列只有一个元素 if( left == right ) { if( nums[left] > 0 ) return nums[left]; else return 0; } //先分 center = ( left + right ) / 2; //递归调用获取左边最大子列和 left.....center MaxLeftSum = MaxSubseqSum3( nums, left, center ); //递归调用获取右边最大子列和 center+1.....right MaxRightSum = MaxSubseqSum3( nums, center+1, right ); //跨边界最大子列和 MaxLeftBorderSum = 0; LeftBorderSum = 0; for( i=center; i>=left; i-- ) { /* 从中线向左扫描 */ LeftBorderSum += nums[i]; if( LeftBorderSum > MaxLeftBorderSum ) MaxLeftBorderSum = LeftBorderSum; } /* 左边扫描结束 */ MaxRightBorderSum = 0; RightBorderSum = 0; for( i=center+1; i<=right; i++ ) { /* 从中线向右扫描 */ RightBorderSum += nums[i]; if( RightBorderSum > MaxRightBorderSum ) MaxRightBorderSum = RightBorderSum; } /* 右边扫描结束 */ /* 下面返回"治"的结果 */ return getmaxint3( MaxLeftSum, MaxRightSum, MaxLeftBorderSum + MaxRightBorderSum ); }
算法4：在线处理法
int MaxSubseqSum4(int A[], int N) { int ThisSum, MaxSum; int i; ThisSum = MaxSum = 0; for( i = 0; i < N; i++) { ThisSum += A[i]; if( ThisSum > MaxSum) MaxSum = ThisSum; else if(ThisSum < 0) ThisSum = 0; } return MaxSum; } //T(N) = O(N);
———————————————— 版权声明：本文为博主「Sofar」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。 原文链接：https://sofar1994.github.io/post/19111/
