首页 > 代码库 > leetCode 53. maximum subarray
leetCode 53. maximum subarray
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [-2,1,-3,4,-1,2,1,-5,4]
,
the contiguous subarray [4,-1,2,1]
has the largest sum = 6
.
贪婪算法找每个当前位置对应的最大的subarray,
class Solution {public: int maxSubArray(vector<int>& nums) { int n=nums.size(); vector<int> eachnum; int sum=0; for(int i=0;i<n;i++) { if(sum<0) { sum=0; } sum+=nums[i]; eachnum.push_back(sum); cout<<sum<<endl; // eachnum[i]=sum; } vector<int>:: iterator biggest=max_element(eachnum.begin(),eachnum.end()); return *biggest; }};
更简单的方法,记录当前最大的结果,因为每遇到一个数,可能有两种可能,一是加这个数,二是从这个数开始。 那我们就要找当前的最优情况与历史最优情况比较。
和可能的结果:
class Solution {public: int maxSubArray(vector<int>& nums) { int adj_sum = 0; int cont_sum = nums[0]; for (vector<int>::iterator it = nums.begin(); it<nums.end(); it++) { adj_sum+=*it; adj_sum = max(adj_sum, *it);//记录加当前数与从当前数开始的最大值 cont_sum = max(cont_sum, adj_sum);// 比较当前的最大值与历史最大值,记录最大值 } return cont_sum; }};
这是一个最优化问题,最优化问题一般都可以用DP(动态规划)解决。 对于动态规划,要考虑子问题是什么(形式的子问题或状态的子问题)子问题就可以用recursive solution。
- 对于 maxSubArray( int a[], int i,int j), is searching for the maxSubArray for a[i:j]
- the goal is to figure out what maxSubArray(A,0,A.length()-1) is.
- 对于maxSubArray(int a[], int i, int j) is difficult ot connect this sub problem to the original, so we change the format of the sub problem to maxSubArray(int a[], int i), which means the maxSubArray for A[0:i]. which must has A[i] as the end. so we should keep track of each solution of the sub problem to update the global optimal value.
maxSubArray(A,i)=maxSubArray(A, i-1)>0?maxSubArray(A, i-1):0+A[i];
so the solution is same as the previous one:
int maxSubArray(vector<int> & nums) { int n=nums.size(); int num=0; int* dp=new int[n]; dp[0]=nums[0]; int maxsum=nums[0]; for (int i=1;i<n;i++) { if(dp[i-1]<0) dp[i]=nums[i]; else dp[i]=dp[i-1]+nums[i]; cout<<dp[i]<<" "<<dp[i-1]<<endl; maxsum=max(maxsum,dp[i]); cout<<maxsum<<endl; } return maxsum; }
开始写 dp[i]=nums[i]+dp[i-1]>0?dp[i-1]:0; 有错哈哈, 忘了带括号
dp[i]=nums[i]+(dp[i-1]>0?dp[i-1]:0);
leetCode 53. maximum subarray
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。