首页 > 代码库 > [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.
click to show more practice.
More practice:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
【分析】
无
【代码】
/*********************************
* 日期：2015-01-27
* 作者：SJF0115
* 题目: 53.Maximum Subarray
* 网址：https://oj.leetcode.com/problems/maximum-subarray/
* 结果：AC
* 来源：LeetCode
* 博客：
**********************************/
#include <iostream>
#include <climits>
using namespace std;
class Solution {
public:
int maxSubArray(int A[], int n) {
if(n <= 0){
return 0;
}//if
// 最大和
int max = A[0];
// 当前最大和
int cur = 0;
for(int i = 0;i < n;++i){
// 一旦当前最大和小于0就重置为0,一个负数只能使最大和变小
if(cur < 0){
cur = 0;
}//if
cur += A[i];
if(cur > max){
max = cur;
}//if
}//for
return max;
}
};
int main(){
Solution solution;
int n = 9;
int A[] = {-2,1,-3,4,-1,2,1,-5,4};
int result = solution.maxSubArray(A,n);
// 输出
cout<<result<<endl;
return 0;
}
[LeetCode]53.Maximum Subarray
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。