題目

對于長度為N的數組A，求連續子數組的和最接近0的值。

如：

數組A：1，-2,3,10，-4,7,2，-5

它是所有子數組中，和最接近0的是哪個？

算法流程

申請比A長1的空間sum[-1,0,...,N-1]，sum[i]是A的前i項和。定義sum[-1]=0

顯然有：A的i到j項和=sum(j)-sum(i-1)

算法思路：

對sum[-1,0,...,N-1]排序，然后計算sum相鄰元素的差的絕對值，最小即為所求

在A中任意取兩個前綴子數組的和，求差的最小值。

討論

計算前n項和數組sum和計算sum相鄰元素差的時間復雜度，都是O（N），排序的時間復雜度認為是O（N*logN），因此，總時間復雜度：O（NlogN）。

思考：如果需要返回絕對值最小的子數組本身呢？

代碼如下

int MinSubarray(const int* a, int size) {int* sum = new int[size + 1];sum[0] = 0;int i;for (i = 0; i < size; i++){sum[i + 1] = sum[i] + a[i];}sort(sum, sum + size + 1);int difference = abs(sum[1] - sum[0]);int result = difference;for (i = 1; i < size; i++){difference = abs(sum[i + 1] - sum[i]);result = min(difference, result);}delete[] sum;return result; }

下面來看一下最大連續子數組的問題

給定一個數組A[0,...,n-1],求A的連續子數組，使得該子數組的和最大。

例如：數組1，-2,3,10，-4,7,2，-5最大子數組：3,10，-4,7,2

分析

記S[i]為以A[i]結尾的數組中和最大的子數組，則：S[i+1]=max(S[i]+A[i+1],A[i+1])

S[0]=A[0]

遍歷i：0<=i<=n-1

動態規劃：最優子問題

時間復雜度O（n）

代碼如下

int MaxSubarray(const int* a, int size) {if (!a || (size <= 0))return 0;int sum = a[0]; // 當前子串的和int result = sum; // 當前找到的最優解for (int i = 1; i < size; i++){if (sum > 0){sum += a[i];}else{sum = a[i];}result = max(sum, result);}return result; }

求最大子數組還有一種思路如下：

定義：前綴和sum[i]=a[0]+a[1]+...+a[i]則：a[i,j]=sum[j]-sum[i-1](定義p[-1]=0)，最大子數組=sum(j)-sum(i-1)

算法過程

• 求i前綴sum[i]:
  • 遍歷i：0<=i<=n-1
  • sum[i]=sum[i-1]+a[i]
• 計算以a[j]結尾的子數組的最大值
  • 對于某個j：遍歷0<=i<=j，求sum[i]的最小值m
  • sum[j]-m即為a[j]結尾的數組中最大的子數組的值
• 統計sum[j]-m的最大值，0<=j<=n-1
  • 1,2,3步都是線性的，因此，時間復雜度O（n）。

如果要求子數組本身，只需要記錄一下from和to就可以了

總結

以上是生活随笔為你收集整理的算法学习-零子数组，最大连续子数组的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。