題目給定一個整數陣列，要求找到一個連續的子陣列，這個子陣列的和是所有子陣列中最大的，並回傳該總和值。
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example:
Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6.
Follow up:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
解題思路:
我們先設定兩個參數
current: 存放目前元素的子陣列和
result: 存放已計算過後的最大子陣列和
current與result一開始皆設於nums[0]
使用一個迴圈從i=1開始遍歷nums陣列
不斷將current與下一個陣列元素進行相加
相加的結果小於0或小於下一個陣列元素則將current的數值設為下一個陣列元素
如果current數值大於result則更新result數值
此題時間複雜度為O(N)、空間複雜度為O(1)
如果用暴力解，連續子陣列數是 N+(N-1)+(N-2)+…+1，時間複雜度為O(N²)。
using System;
namespace Maximum_Subarray_Easy
{
class Program
{
static void Main(string[] args)
{
int[] nums = new int[] { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
int result = maxSubArray(nums);
Console.WriteLine(result);
}
public static int maxSubArray(int[] nums)
{
int result = nums[0];
int current = nums[0];
for (int i = 1; i < nums.Length; i++)
{
current += nums[i];
if (current < 0 || current < nums[i])
current = nums[i];
if (current > result)
result = current;
}
return result;
}
}
}