【LeetCode】053.最大子序和 (Maximum Subarray) 動态規劃/分治法

題目描述

給定一個整數數組 nums ，找到一個具有最大和的連續子數組（子數組最少包含一個元素），傳回其最大和。

示例：

輸入: [-2,1,-3,4,-1,2,1,-5,4],

輸出: 6

解釋: 連續子數組 [4,-1,2,1] 的和最大，為 6。

進階:

如果你已經實作複雜度為 O(n) 的解法，嘗試使用更為精妙的分治法求解。

解決方法

方法一：動态規劃

dp[i] 裡儲存以第i個數結尾的最大子序和（包括第 i 個數）。

初始化 dp[0]=nums[0] ；

狀态轉移： dp[i-1]>0 時，dp[i]=dp[i-1]+nums[i] ；

      dp[i-1]<=0 時，dp[i]=nums[i] ，重新開始新子數組求和。

時間複雜度： O(n)

實作代碼：

class Solution
{
public:
	int maxSubArray(vector<int>& nums)
	{
        vector<int> dp(nums.size());
		
		dp[0] = nums[0];
		int ans = dp[0];
		for (int i = 1; i < nums.size(); i++)
		{
			if (dp[i - 1] > 0)
				dp[i] = dp[i - 1] + nums[i];
			else
				dp[i] = nums[i];

			ans = max(ans, dp[i]);
		}

		return ans;
	}
};
           

方法二：分治法

将數組 nums[left…right] 在 mid=(left+right)/2 分成兩部分，nums[left…right] 的最大子序和的連續子數組有三種可能的位置：

（1）在分割點左邊，即在 nums[left…mid] 中産生；

（2）在分割點右邊，即在 nums[mid+1…right] 中産生；

（3）跨越兩部分， 即至少同時包括 nums[mid] 和 nums[mid+1] ，從這兩個數向左右擴張。

那麼，nums[left…right] 的最大子序和為三種情況的最大值。第一、二種情況遞歸，第三種情況直接計算。

時間複雜度： O(nlogn)

實作代碼：

class Solution
{
public:
	int maxSubArray(vector<int>& nums)
	{
		return maxSubArrayDC(nums, 0, nums.size() - 1);
	}

	int maxSubArrayDC(vector<int>& nums, int left, int right)
	{
		if (left == right)
			return nums[left];

		int mid = (left + right) / 2;

		int max1 = nums[mid];
		int sum = 0;
		for (int i = mid; i >= left; --i)
		{
			sum += nums[i];
			max1 = max(max1, sum);
		}

		int max2 = nums[mid + 1];
		sum = 0;
		for (int i = mid + 1; i <= right; ++i)
		{
			sum += nums[i];
			max2 = max(max2, sum);
		}

		int ans1 = maxSubArrayDC(nums, left, mid);
		int ans2 = maxSubArrayDC(nums, mid + 1, right);
		int ans3 = max1 + max2;

		return max(ans1, max(ans2, ans3));
	}
};