#35445: N^2 解題法 (暴力解是N^4)
quency89513@gmail.com
(QC Lin)
學校
:
不指定學校
編號 : 205592
來源 : [140.113.195.205]
最後登入時間 ：
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
(林祺祐)
學校
:
高雄市立高雄高級中學
編號 : 186388
來源 : [106.1.66.150]
最後登入時間 ：
2024-10-05 17:31:58
怕大家被誤導
這個作法是 N^3 不是 N^2
(枚舉上界) * (枚舉下界) * (解1D的最大子區間) = O(N^3)
N^3解題法 (通靈解是 N^2)
ZeroJudge Forum