This repository was archived by the owner on Feb 27, 2020. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathmaximum_subarray.h
More file actions
118 lines (111 loc) · 4.71 KB
/
maximum_subarray.h
File metadata and controls
118 lines (111 loc) · 4.71 KB
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
/*************************************************************************************
* MIT License *
* *
* Copyright (C) 2017 Charly Lamothe, Doulkifouli Abdallah-Ali *
* *
* This file is part of MaximumSubarrayProblem. *
* *
* Permission is hereby granted, free of charge, to any person obtaining a copy *
* of this software and associated documentation files (the "Software"), to deal *
* in the Software without restriction, including without limitation the rights *
* to use, copy, modify, merge, publish, distribute, sublicense, and/or sell *
* copies of the Software, and to permit persons to whom the Software is *
* furnished to do so, subject to the following conditions: *
* *
* The above copyright notice and this permission notice shall be included in all *
* copies or substantial portions of the Software. *
* *
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR *
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, *
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE *
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER *
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, *
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE *
* SOFTWARE. *
*************************************************************************************/
#ifndef MAXIMUM_SUBARRAY_H
#define MAXIMUM_SUBARRAY_H
/**
* Find the array with the largest subarray of array T
* of size n.
*
* @param T Array of integers
* @param n Size of T array
* @return k Left index of largest subarray
* @return l Right index of largest subarray
* @return sum Sum of the largest subarray
*
* Algorithm
* Compute all possible subsequences.
* Compute the sum of all subsequences, and keep
* the indices of the largest sum.
* Return the indices by parameter.
*
* Complexity: O(n³)
*/
int maximum_subarray_naive(int *T, int n, int *k, int *l);
/*
* Find the array with the largest subarray of array T
* of size n.
*
* @param T Array of integers
* @param n Size of T array
* @return k Left index of largest subarray
* @return l Right index of largest subarray
* @return sum Sum of the largest subarray
*
* Algorithm
* Compute the subsequences on the fly, and apply the optimization
* S(k, l) = S(k, l - 1) + T[l] avec the line sum += T[j].
*
* Complexity: O(n²)
*/
int maximum_subarray_naive_optimized(int *T, int n, int *k, int *l);
/*
* Find the array with the largest subarray of array T
* of size n.
*
* Algorithm
* Compute the best left sum
* Compute the best right sum
* Compute the best middle sum
* Compute the maximum between the three computed sums
* @param T Array of integers
* @param k L'indice courant du début de T
* @param l L'indice courant de la fin de T
* @return sum Sum of the largest subarray
* @return final_k Left index of largest subarray
* @return final_l Right index of largest subarray
*
* Complexity
* - If k == l : O(1)
* - Divide the problem in two : T(N/2)
* - Compute the middle subsequence : O(N)
* - Resolve the maximum between each sum : O(1)
* Thus T(1) = O(1) and
* For N > 1, T(N) = 2T(N/2) + O(N)
* T(N) = O(NlogN)
*/
void maximum_subarray_divide_conquer(int *T, int k, int l, int *sum, int *final_k, int *final_l);
/**
* Find the array with the largest subarray of array T
* of size n.
*
* Algorithm
* Find the largest continuous sum using the sum variable,
* which is compared to the largest known sum at each iteration
* (by default the first element).
* If the sum is negative, the sum is reinitialized and we
* advance to index k.
* The final sum is the largest found sum.
*
* @param T Array of integers
* @param n Size of T array
* @return k Left index of largest subarray
* @return l Right index of largest subarray
* @return sum Sum of the largest subarray
*
* Complexity: O(n) because there's only a single iteration of T
*/
int maximum_subarray_kadane(int *T, int n, int *k, int *l);
#endif