#35445: N^2 解題法 (暴力解是N^4)

quency89513@gmail.com (QC Lin)

ID : 205592

IP address : [140.113.195.205]

Last Login ：

2023-03-26 17:42:57

/* Solution

http://hanting1225.blogspot.com/2015/11/uva-108-maximum-sum.html

The main idea is to reduce this problem to 1D max sub-sequence sum,

which can be solved with max_subseq_sum().

How to solve 1D max sub-sequence sum:

Given a 1D array, find the max sub-sequence sum.

(sub-sequence should be contiguous in the original array)

e.g.

list[]={-4, 3, 1, -1, 4}, max_sub_seq={3,1,-1,4}, max_sub_sum=7

list[]={4, 9, -17, 1}, max_sub_seq={4,9}, max_sub_sum=13

To find out max_sub_sum, we go through the array once,

every iteration decides if the element should be added to the sub sequence OR

discard the current sub sequence and start from the element.

In the for loop go through the array,

the element should be added to the sub sequence when: the sum of the sub sequence + the element > the element

discard the current sub sequence and start from the element when: the sum of the sub sequence + the element < the element

The idea is if the the current sub sequence + the element is smaller,

than a new sub_seq starting from the element is definitely going to be larger than current sub sequence + the element

e.g.

list[]={-4, 3, 1, -1, -2}

1st iter: sub_seq={-4}, sum = -4

2nd iter: sub_seq={3}, sum = 3, sum(-4,3) < 3, sub_seq discarded and new sub_seq = {3}

3rd iter: sub_seq={3, 1}, sum = 4, sum(3,1) > 1, element 1 added to sub_seq

4th iter: sub_seq={3,1,-1}, sum = 3, sum(3,1,-1) > -1, element -1 added to sub_seq

5th iter: sub_seq={3,1,-1,-2}, sum = 1, sum(3,1,-1,-2) > -2, element -2 added to sub_seq

So the max_sub_seq={3,1} at the 3rd iteration with sum=4

For implementation, we don't have to maintain a such sub_seq[] in the for loop.

Just keep an eye on sum on every iteration, record the maximal value of sum,

and you will get the max sub sequence sum.

If the content of the sub_seq[] is required (which is not in 108_Maximum_Sum),

just record start and end as iteration number i when sum updated (See the code for details).

This solution does not go through every possible sub sequence

but only goes through every possible sub sequence that might be larger than the current sub sequence in hand.

Now we have to reduce 108_Maximum_Sum from 2D to 1D.

Consider the example:

row A A1 A2 A3 A4

row B B1 B2 B3 B4

row C C1 C2 C3 C4

row D D1 D2 D3 D4

If the question is "Find a rectangle that has maximal sum with 4 rows and arbitrary columns",

than the solution will be sum the 2D array by column:

S1 S2 S3 S4, where Sx = sum(Ax+Bx+Cx+Dx)

and max_subseq_sum({S1 S2 S3 S4}) is the answer.

If max_subseq({S1 S2 S3 S4}) is {S2 S3}, than the rectangle will be

A2 A3

B2 B3

C2 C3

D2 D3

Now, the question is "Find a rectanble that has maximal sum with arbirary rows/columns".

Just iterate *(every possible combination of contiguous rows) and repeat:

sum the columns -> {S1 S2 S3 S4}

max_subseq_sum({S1 S2 S3 S4})

*(every possible combination of contiguous rows):

In this example, it would be row A, AB, ABC, ABCD, B, BC, BCD, C, CD, D

*/

#39359: Re: N^2 解題法 (暴力解是N^4)

leolin0214@gmail.com (林祺祐)

ID : 186388

IP address : [106.1.66.150]

Last Login ：

2024-07-24 10:39:17

怕大家被誤導

這個作法是 N^3 不是 N^2

(枚舉上界) * *(*枚舉下界*) ** (解1D的最大子區間) = O(N^3)

N^3解題法 (通靈解是 N^2)

ZeroJudge Forum