從陣列中找出元素值加總為最大的子陣列。
題目
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
先想到的解法
比對所有可能的子陣列的加總。用迴圈遍歷陣列，內部再以另一個迴圈遍歷外迴圈目前索引後的元素並累加，每次加總的結果與上一次加總比較，若數值比較大就暫存起來用來和下一次的加總進行比較。內外迴圈時間複雜度為O(n^2)。
nums=[5,4,-1]
==============================outter:L1, inner:L1=============================
v (i=0)
nums=[5,4,-1]
^ (j=i)
sum=5
max=5
==============================outter:L1, inner:L2=============================
v (i=0)
nums=[5,4,-1]
^ (j=i+1)
sum=9
max=9
==============================outter:L1, inner:L3=============================
v (i=0)
nums=[5,4,-1]
^ (j=i+2)
sum=4
max=9
==============================outter:L2, inner:L1=============================
v (i=1)
nums=[5,4,-1]
^ (j=i)
sum=4
max=9
==============================outter:L2, inner:L2=============================
v (i=1)
nums=[5,4,-1]
^ (j=i+1)
sum=3
max=9
==============================outter:L3, inner:L1=============================
v (i=2)
nums=[5,4,-1]
^ (j=i)
sum=-1
max=9
Main.java
package com.abc.demo;
public class Main {
public static void main(String[] arges) {
System.out.println((maxSubArray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4})));
System.out.println((maxSubArray(new int[]{1})));
System.out.println((maxSubArray(new int[]{5, 4, -1, 7, 8})));
System.out.println((maxSubArray(new int[]{-2, 1})));
}
public static int maxSubArray(int[] nums) {
int max = nums[0];
for (int i = 0; i < nums.length; i++) {
int sum = nums[i];
for (int j = i; j < nums.length; j++) {
if (j > i) {
sum += nums[j];
}
if (sum > max) {
max = sum;
}
}
}
return max;
}
}
上面在LeetCode無法通過因為Time Limit Exceeded，當陣列長度變長效率立刻變很差。題目的陣列長度最長為105即100,000，也就是時間複雜度O(n^2)最多可能跑10,000,000,000次（一百億次）。
更加解
Kadane算法
想不出更加解後參考別人的答案解法，用一個廽圈遍歷陣列並依序累加元素值，每一次加總sum與上一次加總比較，若此次加總數值較大則存至max，若加總為負值則歸0。剛開始看搞不懂為甚麼這解法可找出所有子陣列加總的最大值，想了一陣子才搞清楚。重點在每一次加總為負值則歸0，當前面連續元素（即子陣列）的加總為負時若繼續累加只會讓之後的子陣列的加總變小而不會變大，因此屏棄前面加總為負的子陣列，而把sum歸0代表從目前遍歷到的元素重新開始繼續往後累加並比較。時間複雜度O(n)。
nums=[1,-2,3,-1]
L1:=================================================================
v (i=0)
nums=[1,-2,3,-1]
sum=1 (1)
max=1
L2:=================================================================
v (i=1)
nums=[1,-2,3,-1]
sum=-1 (1-2)
max=1
set sum to 0
L3:=================================================================
v (i=2)
nums=[1,-2,3,-1]
sum=3
max=3
L3:=================================================================
v (i=3)
nums=[1,-2,3,-1]
sum=2 (3-1)
max=3
Main.java
package com.abc.demo;
public class Main {
public static void main(String[] arges) {
System.out.println((maxSubArray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}))); // 6
System.out.println((maxSubArray(new int[]{1}))); // 1
System.out.println((maxSubArray(new int[]{5, 4, -1, 7, 8}))); // 23
System.out.println((maxSubArray(new int[]{-2, 1}))); // 1
}
public static int maxSubArray(int[] nums) {
int max = nums[0]; // 存放子陣列加總的最大值
int sum = 0; // 子陣列加總
for (int i = 0; i < nums.length; i++) {
sum += nums[i]; // 累加元素值
if (max < sum) { // 若此次加總大於上一次則存起來
max = sum;
}
if (sum < 0) { // 若此次加總為負則歸0
sum = 0;
}
}
return max;
}
}
想說怎麼那麼難，回頭一看發現是medium的題目，這應該算是我第一次做的medium題目。又查了一下發現這解法稱為Kadane's演算法。
Divide and conquer 分治法
另一個解法為利用分治法又稱divide and conquer來找出有最大加總的子陣列。分治法把原陣列從中間拆分為二，並利用遞迴將分為二的子陣列繼續拆分直到找出結果。
下面圖示用分治法從[-1,2,3,-2,1]得出最大加總子陣列為[2,3]的加總5。紅圈為每次分拆陣列比較後回傳的最大加總的元素。時間複雜度O(n log(n))。
作法為從陣列的一半切為左右兩份，[-1,2,3,-2,1]分為
左：[-1,2,3]；
右：[-2,1]。
計算左右兩邊從中間往外累加的最大加總(Cross Max)。左邊累加最大為5，右邊累加最大為-1，加總為4。
左邊的子陣列[-1,2,3]繼續拆為
左：[-1,2]；
右：[3]。
計算Cross Max。左邊累加最大為2，右邊累加最大為3，加總為5。
左邊的子陣列[-1,2]繼續拆為
左：[-1]；
右：[2]。
計算Cross Max。左邊累加最大為-1，右邊累加最大為2，加總為1。
拆到子陣列剩一個元素時即為該側最大並回傳，此為遞迴的終止，因此回傳到上個陣列[-1,2]的
左邊最大(Left Max)為[-1]；
右邊最大(Right Max)為[2]。
比較子陣列[-1,2]的左邊最大-1、右邊最大2與Cross Max1並回傳最大的結果為2即為上個陣列[-1,2,3]的左邊最大。
比較子陣列[-1,2,3]的左邊最大2、右邊最大3與Cross Max5並回傳最大的結果為5即為上個陣列[-1,2,3,-2,1]的左邊最大。
比較陣列[-1,2,3,-2,1]的左邊最大5、右邊最大1與Cross Max4並回傳最大的結果為5即為最大的子陣列加總。
剛開始較難難理解Cross Max，其作用為因爲左右分拆子陣列的最大並不一定是原陣列的最大，真的最大可能是橫跨左右兩側的元素加總，因此要計算Cross Max並與左右子陣列的最大比較得出最大的結果。
┌────────────────┐
│ CM = Cross Max │
│ RM = Right Max │
│ LM = Left Max │
└────────────────┘
│
*LM=5 ┌───┬───┬───┼───┬───┐
RM=1 │-1 │ 2 │ 3 │-2 │ 1 │
CM=(5-1)=4 └───┼───┼───┼───┼───┤
└───────┼───────┘
5 │ -1
│ │
LM=2 ┌───┬───┼───┐ ┌───┼───┐ LM=-2
RM=3 │-1 │ 2 │ 3 │ │-2 │ 1 │ *RM=1
*CM=(2+3)=5 └───┼───┼───┤ ├───┼───┤ CM=(-2+1)=-1
└───┼───┘ └───┼───┘
2 │ 3 -2 │ 1
│
LM=-1 ┌───┼───┐ ┌───┐ ┌───┐ ┌───┐
*RM=2 │-1 │ 2 │ │ 3 │ │-2 │ │ 1 │
CM=(-1+2)=1 ├───┼───┤ └───┘ └───┘ └───┘
└───┼───┘
-1 │ 2
┌───┐ ┌───┐
│-1 │ │ 2 │
└───┘ └───┘
Main.java
package com.abc.demo;
public class Main {
public static void main(String[] arges) {
System.out.println((maxSubArray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4})));
System.out.println((maxSubArray(new int[]{1})));
System.out.println((maxSubArray(new int[]{5, 4, -1, 7, 8})));
System.out.println((maxSubArray(new int[]{-2, 1})));
}
public static int maxSubArray(int[] nums) {
return maxSubArray(nums, 0, nums.length - 1);
}
public static int maxSubArray(int[] nums, int start, int end) {
if (start == end) { // 頭尾索引相同代表陣列只有一個元素
return nums[start];
}
int mid = (start + end) / 2; // 取得目前頭尾索引中間的索引
int crossMax = getCrossMax(nums, mid);
int leftMax = maxSubArray(nums, start, mid); // 遞迴找出左邊子陣列的最大
int rightMax = maxSubArray(nums, mid + 1, end); // 遞迴找出又邊子陣列的最大
return Integer.max(Integer.max(leftMax, rightMax), crossMax);
}
public static int getCrossMax(int[] nums, int mid) {
// 計算從中往左的累加最大
int crossMax = nums[mid];
int leftSum = crossMax;
for (int i = mid - 1; i >= 0; i--) {
leftSum += nums[i];
if (leftSum > crossMax) {
crossMax = leftSum;
}
}
// 計算從中往右的累加最大
int rightSum = crossMax;
for (int j = mid + 1; j < nums.length; j++) {
rightSum += nums[j];
if (rightSum > crossMax) {
crossMax = rightSum;
}
}
return crossMax;
}
}
只能說想出這麼精妙算法的人真的是天才，凡人如我只能靠練習。
題目變化
改為回傳為加總最大值的子陣列，例如[-2,1,-3,4,-1,2,1,-5,4]回傳[4,-1,2,1]。
沒有留言:
張貼留言