最大子序列和c++
以下是使用C++實現最大子序列和的代碼:
#include <iostream>
#include <vector>
using namespace std;
int maxSubArraySum(vector<int>& nums) {
int n = nums.size();
int max_so_far = nums[0];
int curr_max = nums[0];
for (int i = 1; i < n; i++) {
curr_max = max(nums[i], curr_max + nums[i]);
max_so_far = max(max_so_far, curr_max);
}
return max_so_far;
}
int main() {
vector<int> nums = {-2, 1, -3, 4, -1, 2, 1};
int result = maxSubArraySum(nums);
cout << "Maximum subarray sum is: " << result << endl;
return 0;
}
該算法使用動態規劃的思想,通過維護兩個變數max_so_far
和curr_max
來記錄當前最大子序列的和和當前最大子序列中當前位置之前的最大和。對於每個位置,如果當前元素加上之前最大和的值大於當前位置之前的最大和,則更新當前最大和的值;否則,將當前元素加入當前最大子序列中。最終返回max_so_far
即可得到最大子序列的和。