Gepostet vor Aktualisiert vor ALGORITHM6 minutes lesen (Über 952 Wörter)

求解最大子数组

暴力破解法

通过遍历每个子数组，找到最小的子数组

算法复杂度 $$n^2$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func FindMaxSubArr(A []int) (int, int, int) {
	var max = A[0]
	var current = 0
	var left, right = 0, 0
	var LengthA = len(A)
	for i := 0; i < LengthA; i++ {
		current = A[i]
		if current > max { // 判断初始的单元是否是最大数组,第一次写的时候忘记加了，导致有些排列会出问题
			max = current
			left, right = i, i
		}
		for k := i + 1; k < LengthA; k++ {
			current += A[k]
			if current > max {
				max = current
				left, right = i, k
			}
		}
	}

	return left, right, max
}

分治法

分解数组规模，递归的求解左右子数组及跨越中间的数组。
将数组分为两部分，最大子数组要么在左边的子数组，要么在右边的子数组，要么跨越两个子数组

算法复杂度 $$n log(n)$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
func FindMaxSubArr(A []int) (int, int, int) {
	if len(A) == 1 {
		return 0, 0, A[0]
	}
	middle := len(A) / 2
	ll, lr, lm := FindMaxSubArr(A[:middle])
	rl, rr, rm := FindMaxSubArr(A[middle:])
	ml, mr, mm := FindCrossMiddleSubArr(A[:])

	if lm >= rm && lm >= mm {
		return ll, lr, lm
	} else if rm >= lm && rm >= mm {
		return rl + middle, rr + middle, rm
	} else {
		return ml, mr, mm
	}
}

func FindCrossMiddleSubArr(A []int) (int, int, int) {
	lens := len(A)
	if lens == 1 {
		return 0, 0, A[0]
	}
	middle := lens / 2
	left, right := middle-1, middle
	lmax, rmax := A[left], A[right]
	ltemp := lmax
	rtemp := rmax
	i := left
	k := right
	for i > 0 {
		i--
		ltemp += A[i]
		if lmax < ltemp {
			lmax = ltemp
			left = i
		}
	}

	for k < lens-1 {
		k++
		rtemp += A[k]
		if rmax < rtemp {
			rmax = rtemp
			right = k
		}
	}

	return left, right, lmax + rmax
}

动态规划

若已知 A[1.. j] 的最 大子数组，基于如下性质将解扩展为 A[1. .j+1] 的最大子数组： A[1. .j+1] 的最大子数组要么是 A[1.. j] 的最大子数组，要么是某个子数组 A[i.. j+1])
简单的理解，给一个已知最大子数组的数组增加一个单元，新数组的最大子数组如果产生了变化，会有两种情况：

  1. 最大子数组不变
  2. 最大子数组内包含新增的单元

初版错误的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func FindMaxSubArr(A []int) (int, int, int) {
	max := A[0]
	left, right := 0, 0

	leftToNow := max
	tempLeft := left
	for i := 1; i < len(A); i++ {
		leftToNow = leftToNow + A[i]
		if leftToNow > max && leftToNow > A[i] {
			max = leftToNow
			left = tempLeft
			right = i
		} else if A[i] > leftToNow && A[i] > max {
			max = A[i]
			leftToNow = max
			left, right = i, i
			tempLeft = left
		}
	}

	return left, right, max
}

随机测试发现 类似序列 [-8 -4 6 -8 5 7 -5 6 -1 -7] 并不能正常生成最大子数组。
问题在于左界只会因为之前的子数组小于当前单元时会右移重置，会导致计算的最大子数组中包含了左侧连续的和为负的子数组，导致整体的和变小。
解决这个问题，我们需要知道。 x < 0, x + P <= P
我们需要动态的舍去已经计算出的负数子数组。当前子数组的和已经小于零，那么不论下一个单元是正是负，都会大于或者等于当前的子数组的合。

1
2
3
4
 else if leftToNow < 0 {
    leftToNow = 0
    tempLeft = i + 1
}

再次测试的时候，发现还是有问题，问题出在这两行

1
2
3
if leftToNow >= max && leftToNow > A[i]

} else if A[i] > leftToNow && A[i] > max {

我们仅当 leftNow > A[i] 时才更新 max, 但是通过上面的代码，我们可能已经将leftToNow 更新成了 A[i] , 因此它将永远不会成立。
我们只需要将两个条件中的任意一个 leftToNow 与 A[i] 的比较进行 == 的判断就可以了

算法复杂度 $$n$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func FindMaxSubArr(A []int) (int, int, int) {
	max := A[0]
	left, right := 0, 0

	leftToNow := max
	tempLeft := left
	for i := 1; i < len(A); i++ {
		leftToNow = leftToNow + A[i]
		if leftToNow > max && leftToNow >= A[i] {
			max = leftToNow
			left = tempLeft
			right = i
		} else if A[i] > leftToNow && A[i] > max {
			max = A[i]
			leftToNow = max
			left, right = i, i
			tempLeft = left
		} else if leftToNow < 0 {
			leftToNow = 0 // 循环开始时会被初始化为 A[i+1] 的值，不会产生负面影响
			tempLeft = i + 1
		}
	}

	return left, right, max
}

实际上 如果采用 

1
} else if A[i] >= leftToNow && A[i] > max {

tempLeft = i + 1 也是可以省略的

Gepostet vor Aktualisiert vor ALGORITHM3 minutes lesen (Über 495 Wörter)

一元多项式的乘法与加法运算(数组解法)

02-线性结构2 一元多项式的乘法与加法运算

设计函数分别求两个一元多项式的乘积与和。

输入格式:

输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。

输出格式:

输出分2行，分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。零多项式应输出 0 0。

输入样例:

1
2
4 3 4 -5 2  6 1  -2 0
3 5 20  -7 4  3 1

输出样例:

1
2
15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 1
5 20 -4 4 -5 2 9 1 -2 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <stdio.h>

void putX(int A[][2], int numA, int B[][2], int numB);
void putSum(int A[][2], int numA, int B[][2], int numB);
int main(){
    int num1, num2;
    scanf("%d", &amp;num1);
    int Arr1[num1][2];
    for(int i = 0; i < num1; i++){
        scanf("%d", &amp;Arr1[i][0]);
        scanf("%d", &amp;Arr1[i][1]);
    }
    scanf("%d", &amp;num2);
    int Arr2[num2][2];
    for(int i = 0; i < num2; i++){
        scanf("%d", &amp;Arr2[i][0]);
        scanf("%d", &amp;Arr2[i][1]);
    }
    putX(Arr1, num1, Arr2, num2);
    putSum(Arr1, num1, Arr2, num2);
    return 0;
}

void putX(int A[][2], int numA, int B[][2], int numB){
    if(numA == 0 || numB == 0){
        printf("0 0\n");
        return;
    }
    int max = A[0][1] + B[0][1] + 1;
    int Arr[max];
    for(int i = 0; i < max; i++){
        Arr[i] = 0;
    }
    for(int i = 0; i < numA; i++){
        for(int k = 0; k < numB; k++){
            Arr[A[i][1] + B[k][1]] += A[i][0] * B[k][0];
        }
    }
    int isNeedSpace = 0;
    for(int i = max -1; i > -1; i--){
        if(Arr[i] == 0) continue;
        if(isNeedSpace){
            printf(" ");
        }
        printf("%d %d", Arr[i], i);
        isNeedSpace = 1;
    }
    printf("\n");
    return;
}

int compote(int a, int b){
    if(a == b){
        return 0;
    }else if( a > b){
        return 1;
    }else{
        return -1;
    }
}

void putSum(int A[][2], int numA, int B[][2], int numB){
    int i = 0, k = 0, isEmpty = 1, isNeedSpace = 0;
    while(i < numA &amp;&amp; k < numB){
        int ps = compote(A[i][1], B[k][1]);
        int sum;
        switch(ps){
            case 0:
                sum = A[i][0] + B[k][0];
                if(sum == 0){
                    i++;
                    k++;
                    continue;
                };
                if(isNeedSpace) printf(" ");
                printf("%d %d", sum, A[i][1]);
                isNeedSpace = 1;
                isEmpty = 0;
                i++;
                k++;
                break;
            case 1:
                if(isNeedSpace) printf(" ");
                printf("%d %d", A[i][0], A[i][1]);
                isNeedSpace = 1;
                isEmpty = 0;
                i++;
                break;
            case -1:
                if(isNeedSpace) printf(" ");
                printf("%d %d", B[k][0], B[k][1]);
                isNeedSpace = 1;
                isEmpty = 0;
                k++;
                break;
        }
    }
    if(i < numA){
        for(;i < numA;i++){
            if(isNeedSpace){
                printf(" ");
            }
            printf("%d %d", A[i][0], A[i][1]);
            isEmpty = 0;
            isNeedSpace = 1;
        }
    }else if(k < numB){
        for(;k < numB;k++){
            if(isNeedSpace){
                printf(" ");
            }
            printf("%d %d", B[k][0], B[k][1]);
            isEmpty = 0;
            isNeedSpace = 1;
        }
    }
    if(isEmpty){
        printf("0 0");
    }
    return;
}
Folgen

Kategorien

Archive

Letzte Einträge

Tags

cloudflare1
codeigniter1
codeigniter42
cors1
dcatadmin1
docker1
go1
htop1
laravel3
losf1
mail1
php1
plugin1
proxy1
puppeteer1
redis1
typecho1
ubuntu1
vmware1
wsl1
安全1
数据恢复1

Links

×