Create Time: 13th May 2024
Title: "[[DAA-Programming-Assignment]]"
status: DONE
Author:
- Junya YANG
tags:
- DAA
- Assignment
- DP
- Document
created: 2024-05-13T01:23
updated: 2024-06-11T01:14
The Maximum Subarray Sum problem seeks to find the contiguous subarray (containing at least one number) which has the largest sum among all possible subarrays of a given integer array.
Define
where
The pseudocode for the Dynamic Programming solution of this problem is as follows:
Algorithm MCS
function MCS(S)
if S is empty then
return 0
end if
F[0]←S[0]
maxSum←S[0]
for i←1 to length(S)−1 do
F[i]←max(F[i−1]+S[i],S[i])
if F[i]>maxSum then
maxSum←F[i]
end if
end for
return maxSum
end function
Initialization: The initialization of F[0]
and maxSum
takes constant time,
Loop: The loop runs maxSum
) take constant time.
Overall: The overall time complexity of the algorithm is
The implementation was performed using standard C and compiled with the GCC compiler.
Directory Structure
To compile the code, ensure you are in the correct directory. If you are in the correct path, you could see the following file tree structure:
.
├── Makefile
├── README.md
├── in
├── in_out
├── lib.c
├── lib.h
├── lib.o
├── mcs
├── mcs.c
└── mcs.o
Compile the Code:
Once you have confirmed the directory structure, simply type make
in the terminal:
make
This command will compile the source files and should produce the following output:
gcc -c mcs.c
gcc -c lib.c
gcc mcs.o lib.o -o mcs
After compiling the code, you can execute the program by entering the following command in the terminal:
./mcs <InputFilename>
For example, to run the program with the input file named in
, type:
./mcs in
This command will run the program using the data specified in the in
file. Make sure that the input file is in the correct format and location as expected by the program.