Last active
January 6, 2019 00:16
-
-
Save qiaoxu123/310c3b82d89cf9884b9e0778bf090451 to your computer and use it in GitHub Desktop.
给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 示例: 输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。 参考链接:https://blog.csdn.net/DERRANTCM/article/details/46736967
剑指offer面试题42
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//思路:累积和(prefix_sum) | |
//时间:8 ms | |
class Solution { | |
public: | |
int maxSubArray(vector<int>& nums) { | |
if (nums.size() < 0) return 0; | |
int prefix_sum = 0; | |
int min_sum = 0; | |
int result = INT_MIN; | |
for (auto n : nums) { | |
prefix_sum += n; | |
result = max(result, prefix_sum - min_sum); | |
min_sum = min(prefix_sum, min_sum); | |
} | |
return result; | |
} | |
}; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//思路:动态规划(dynamic programming) | |
//时间:8 ms | |
class Solution { | |
public: | |
int maxSubArray(vector<int>& nums) { | |
if (nums.size() < 0) return 0; | |
int n = nums.size(); | |
vector<int> dp(n, 0); | |
dp[0] = nums[0]; | |
for (int i = 1; i != n; ++i) { | |
dp[i] = max(0, dp[i-1]) + nums[i]; | |
} | |
int max_value = INT_MIN; | |
for (auto v : dp) { | |
max_value = max(v, max_value); | |
} | |
return max_value; | |
} | |
}; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//思路:贪心算法(greedy solution) | |
//时间:8 ms | |
class Solution { | |
public: | |
int maxSubArray(vector<int>& nums) { | |
if (nums.size() == 0) return 0; | |
int n = nums.size(); | |
int sum = 0; | |
int slice = INT_MIN; | |
for (auto n : nums) { | |
sum += n; | |
slice = max(sum, slice); | |
sum = max(0, sum); | |
} | |
return slice; | |
} | |
}; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//思路:剑指offer | |
//时间:12 ms | |
class Solution { | |
public: | |
int maxSubArray(vector<int>& nums) { | |
int maxSum = INT_MIN; | |
int sum = 0; | |
for(int i = 0;i < nums.size();++i){ | |
if(sum <= 0) | |
sum = nums[i]; | |
else | |
sum += nums[i]; | |
if(sum > maxSum) | |
maxSum = sum; | |
} | |
return maxSum; | |
} | |
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment