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

DAA-Programming-Assignment

1. Formal Definition of the Problem

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.

2. Recurrence Relation

Define as the maximum sum of a subarray ending at index . The recurrence relation can be expressed as:

where is the value of the array at index .

3. Definitions of Notations

: The input array containing integers.
: The maximum sum of a subarray ending at position in array .
: A function returning the maximum of its arguments.

4. Pseudocode

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] \gets S[0]$

$maxSum \gets S[0]$

for $i \gets 1$ to $\text{length}(S) - 1$ do

$F[i] \gets \max(F[i-1] + S[i], S[i])$

if $F[i] > maxSum$ then

$maxSum \gets F[i]$

end if

end for

return $maxSum$

end function

5. Time Cost Analysis

Initialization: The initialization of F[0] and maxSum takes constant time, .
Loop: The loop runs times if is the length of the array. Within each iteration, the operations (calculating and updating maxSum) take constant time.
Overall: The overall time complexity of the algorithm is , where is the number of elements in the input array, as each element is processed exactly once.

6. Bonus Part

This documentation was written in a Markdown file.
In my code, it can output all optimal solutions, both on the screen and to an output file.
The number of integers in the input is unknown. You can input an array of arbitrary size.
Here's a refined version of the guideline section of your documentation:

7. Guidelines about the Code

The implementation was performed using standard C and compiled with the GCC compiler.

Compile

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
```

Run

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.