Algorithm about SubArrays & SubStrings

No.1 Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

e.g. [−2,1,−3,4,−1,2,1,−5,4] -> [4,−1,2,1] = 6.

 1 public void maxSubSimple(int[] array) {
 2     if (array == null || array.length == 0) {
 3         System.out.println("empty array");
 4     }
 5     int max = array[0], cursum = array[0];
 6     for (int i = 1; i < array.length; i++) {
 7         cursum = cursum > 0 ? cursum + array[i] : array[i];
 8         max = max > cursum ? max : cursum;
 9     }
10     System.out.println("max sub-array sum is: " + max);
11 }
12 public void maxSubFull(int[] array) {
13     if (array == null || array.length == 0) {
14         System.out.println("empty array");
15     }
16     int max = array[0], cursum = array[0];
17     int start = 0, end = 0;
18     int final_s = 0, final_t = 0;
19     for (int i = 1; i < array.length; i++) {
20         if (cursum < 0) {
21             cursum = array[i];
22             start = i;
23             end = i;
24         } else {
25             cursum = cursum + array[i];
26             end = i;
27         }
28         if (max < cursum) {
29             max = cursum;
30             final_s = start;
31             final_t = end;
32         }
33     }
34     System.out.println("sub Array: ("+final_s+", "+final_t+")");
35     System.out.println("max sub-array sum is: " + max);
36 }

View Code

No.2 Maximum Product Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

e.g. [2,3,-2,4] -> [2,3] = 6.

 1 public int maxProduct(int[] A) {
 2         int premin = A[0], premax = A[0], max = A[0];
 3         for (int i = 1; i < A.length; i++) {
 4             int tmp1 = premin * A[i];
 5             int tmp2 = premax * A[i];
 6             premin = Math.min(A[i], Math.min(tmp1, tmp2));
 7             premax = Math.max(A[i], Math.max(tmp1, tmp2));
 8             max = Math.max(premax, max);
 9         }
10         return max;
11 }

View Code

No.3 LIS (Longest Increasing Subarray)

The increasing subarray does't has to be contiuous nor same diff

e.g. [1, 6, 8, 3, 7, 9] -> [1, 3, 7, 9] = 4

DP, O(n^2)

 1 public void findLIS(int[] array) {
 2     if (array == null || array.length == 0) {
 3         System.out.println("Empty array");
 4         return;
 5     }
 6     int len = array.length;
 7     int[] dp = new int[len];
 8     int lis = 1;
 9     for (int i = 0; i < len; i++) {
10         dp[i] = 1;
11         for (int j = 0; j < i; j++) {
12             if (array[j] < array[i] & dp[j] + 1 > dp[i]) {
13                 dp[i] = dp[j] + 1;
14             }
15         }
16         if (dp[i] > lis) {
17             lis = dp[i];
18         }
19     }
20     System.out.println("length of Longest Increasing Subarray: "+lis);
21 }

View Code

DP + Binary Search, O(nlogn)

维护一个数组 maxval[i]，记录长度为 i+1 的递增子序列中最大元素的最小值，并对于数组中的每个元素考察其是哪个子序列的最大元素，二分更新maxval数组——《编程之美》

 1 public void BinSearch(int[] maxval, int maxlen, int x) {
 2     int left = 0, right = maxlen-1;
 3     while (left <= right) {
 4         int mid = left + (right - left) / 2;
 5         if (maxval[mid] <= x) {
 6             left++;
 7         } else {
 8             right--;
 9         }
10     }
11     maxval[left] = x;
12 }
13 public void LIS(int[] array) {
14     if (array == null || array.length == 0) {
15         System.out.println("Empty array");
16         return;
17     }
18     int len = array.length;
19     int[] maxval = new int[len];
20     maxval[0] = array[0];
21     int maxlen = 1;
22     for (int i = 0; i < len; i++) {
23         if (array[i] > maxval[maxlen-1]) {
24             maxval[maxlen++] = array[i];
25         } else {
26             BinSearch(maxval, maxlen, array[i]);
27         }
28     }
29     System.out.println("length of Longest Increasing Subarray: "+maxlen);
30 }

View Code

No.4 LCS (Longest Common Substring)

p.s. 最长公共子串: 在原字符串中是连续

　　最长公共子序列: 并不要求在原字符串中连续

e.g. [b, a, b], [c, a, b, a] -> [a, b] or [b, a]

 1 public void LCS(String str1, String str2) {
 2     if (str1 == null || str2 == null || str1.length() == 0 || str2.length() == 0) {
 3         System.out.println("The LCS is empty string");
 4         return;
 5     }
 6     int m = str1.length(), n = str2.length();
 7     int[] pre = new int[n];
 8     int[] cur = new int[n];
 9     int max = 0;
10     for (int i = 0; i < m; i++) {
11         for (int j = 0; j < n; j++) {
12             if (str1.charAt(i) == str2.charAt(j)) {
13                 if (i == 0 || j == 0) {
14                     cur[j] = 1;
15                 } else {
16                     cur[j] = pre[j-1] + 1;
17                 }
18                 max = max > cur[j] ? max : cur[j];
19             }
20         }
21         pre = cur;
22         cur = new int[n];
23     }
24     System.out.println(max);
25 }

View Code

No.5 LCS (Longest Common Subsequence)

e.g. [g c c c t a g c g], [g c g c a a t g] -> []

 1 public void LCS(String str1, String str2) {
 2     if (str1 == null || str2 == null || str1.length() == 0 || str2.length() == 0) {
 3         System.out.println("The LCS is empty string");
 4         return;
 5     }
 6     int m = str1.length(), n = str2.length();
 7     int[] cur = new int[n];
 8     int upleft = 0;
 9     for (int i = 0; i < m; i++) {
10         for (int j = 0; j < n; j++) {
11             int tmp = cur[j];
12             if (j == 0) {
13                 cur[j] = str1.charAt(i) == str2.charAt(j) ? 1 : cur[j];
14             } else if (i == 0) {
15                 cur[j] = str1.charAt(i) == str2.charAt(j) ? 1 : cur[j-1];
16             } else {
17                 if (str1.charAt(i) == str2.charAt(j)) {
18                     cur[j] = Math.max(upleft+1, Math.max(cur[j-1], cur[j]));
19                 } else {
20                     cur[j] = Math.max(upleft, Math.max(cur[j-1], cur[j]));
21                 }
22             }
23             upleft = tmp;
24         }
25     }
26     System.out.println(cur[n-1]);
27 }

View Code