1、最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
class Solution { public: int maxSubArray(vector<int>& nums) { if(nums.size() == 0) return -1; int sum = nums[0]; int maxsum = nums[0]; for(int i=1;i<nums.size();++i) { if(sum>0) sum = sum+nums[i]; else sum = nums[i]; if(maxsum < sum) maxsum = sum; } return maxsum; } };
2、最长上升子序列
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入:[10,9,2,5,3,7,101,18]输出: 4 解释: 最长的上升子序列是[2,3,7,101]，它的长度是4.
//方法一：算法复杂度是 n*n
class Solution { public: int lengthOfLIS(vector<int>& nums) { if(nums.empty()) return 0; int res = 0; vector<int> maxLen(nums.size(), 0); for(int i=0;i<nums.size();++i) { for(int j=0;j<i;++j) { if(nums[j]<nums[i] && maxLen[i] < maxLen[j]) maxLen[i] = maxLen[j]; } maxLen[i] = maxLen[i] + 1; if(res < maxLen[i]) res = maxLen[i]; } return res; } };
3、最长上升子序列和
对于每组测试数据，输出其最大上升子序列和。
比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中序列和最大为18，为子序列(1, 3, 5, 9)的和. 你的任务，就是对于给定的序列，求出最大上升子序列和。注意，最长的上升子序列的和不一定是最大的，比如序列(100, 1, 2, 3)的最大上升子序列和为100，而最长上升子序列为(1, 2, 3)。
#include<iostream> #include<cstring> using namespace std; int main() { int N = 0; while(cin>>N) { int result = 0; int nums[N],maxSum[N]; for(int i=0;i<N;++i) cin>>nums[i]; for(int i=0;i<N;++i) { maxSum[i] = nums[i]; for(int j=0;j<i;++j) { if(nums[j]<nums[i] && maxSum[j]+nums[i] > maxSum[i]) maxSum[i] = maxSum[j]+nums[i]; } if(result < maxSum[i]) result = maxSum[i]; } cout<<result<<endl; } return 0; }