Last Updated on 2021-11-25 by Clay
題目
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
A subarray is a contiguous part of an array.
Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4] Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6.
Example 2:
Input: nums = [1] Output: 1
Example 3:
Input: nums = [5,4,-1,7,8] Output: 23
Constraints:
1 <= nums.length <= 105-104 <= nums[i] <= 104
這個題目非常單純，就是在序列當中找到一個元素加總值最大的子序列。
解題思路
我本來一直想些奇怪的方法，但後來看到 Kadane’s Algorithm 這個演算法簡直驚為天人，真是又簡單又好寫。
這是一個一維最大子序列的經典解法，是由卡內基梅隆大學的 Jay Kadane 所提出的線性解法。（O(n)）
這個方法計算每個位置結束點時的正數和，每個位置都基於計算前一個位置的最大子序列值來計算。
很難精確描述，直接看程式碼。
C++ 程式碼
class Solution {
public:
int maxSubArray(vector<int>& nums) {
// Kadane’s Algorithm
int sum = 0;
int ans = INT_MIN;
for (int i=0; i<nums.size(); ++i) {
sum += nums[i];
ans = max(sum, ans);
sum = max(sum, 0);
}
return ans;
}
};Python 程式碼
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
# Kadane’s Algorithm
temp_val = 0
ans = -10000
for n in nums:
temp_val += n
ans = max(temp_val, ans)
temp_val = max(temp_val, 0)
return ans