C++算法-最大子序列和.zip

// ConsoleApplication2.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。 //最大连续子序列 #include <iostream> #include<vector> #include<algorithm> using namespace std; class Solution { public: int max3(int a, int b, int c) { return max(max(a, b), c); } //分治 int maxsubsequence_f(int*nums,int begin,int end){ if (begin == end) { if (nums[begin] > 0) return nums[begin]; else return 0; } int mid = (begin + end)/2; int maxL = 0, maxR = 0, temp = 0,maxMid=0; for (int i = mid; i >= begin; i--) { temp += nums[i]; if(temp>maxL){ maxL = temp; } } temp = 0; for (int i = mid + 1; i <= end; i++) { temp += nums[i]; if (temp > maxR) { maxR = temp; } } maxMid = maxL + maxR; return max3(maxMid,maxsubsequence_f(nums,begin,mid),maxsubsequence_f(nums,mid+1,end)); } //暴力 int maxsubsequence_b(int* nums,int length) { int maxnums=0, temp=0; for (int i = 0; i < length; i++) { for (int j = i; j < length; j++) { temp = 0; for (int k=i;k<=j;k++) { temp += nums[k]; if (temp > maxnums) { maxnums = temp; } } } } return maxnums; } //动态规划 int maxsubsequence_d(int* nums,int length) { int dp[2000]; memset(dp, 0, 2000 * sizeof(int)); for (int i = 1; i <= length; i++) { dp[i] = max(dp[i - 1] + nums[i - 1], nums[i - 1]); } int max = 1; for (int j = 2; j <= length; j++) { if (dp[max] < dp[j]) { max = j; } } return dp[max]; } }; int main() { time_t t; srand((unsigned)time(&t)); int nums[1000] = {}; for (int i = 0; i < 1000; i++) { nums[i] = rand()%100; } int length = 1000; Solution test; cout << test.maxsubsequence_f(nums, 0, length-1)<<endl; cout << test.maxsubsequence_b(nums, length) << endl; cout << test.maxsubsequence_d(nums, length) << endl; }