给定一个整数序列，a0, a1, a2, …… , an（项可以为负数），求其中最大的子序列和。如果所有整数都是负数，那么最大子序列和为0
以下是O(n)的算法
#include<stdio.h>
#define MAX 1050
int main()
{
int n,i;
int a[MAX];
int maxBefore,maxHere;
scanf("%d",&n);
for (i=0;i<n;i++)
scanf("%d",&a[i]);
maxBefore=0;
maxHere=a[0];
int max=a[0];
for(i=0;i<n;i++)
{
if(maxBefore<0)
maxHere=a[i];
else
maxHere=a[i]+maxBefore;
if(maxHere>max)
max=maxHere;
maxBefore=maxHere;
}
if(max<0)
max=0;
printf("%d",max);
}
MIPS汇编
.data
array:.space 4000
.text
li $v0,5
syscall
move $s0,$v0 #use $s0 as n
li $t0 ,0
forinput:
slt $t1,$t0,$s0
beq $t1,$0,endinput
sll $t1,$t0,2
li $v0,5
syscall
sw $v0,0($t1)
addi $t0,$t0,1
j forinput
endinput:
li $t0,0
sll $t1,$t0,2
lw $t1,0($t1)
move $s1,$0# maxBefore=0;
move $s2,$t1 #maxHere=a[0];
move $s3,$t1
for:
slt $t1,$t0,$s0
beq $t1,$0,endfor
slt $t1,$s1,$0
beq $t1,$0,else
sll $t1,$t0,2
lw $t1,0($t1)
move $s2,$t1
else:
sll $t1,$t0,2
lw $t1,0($t1)
add $s2,$s1,$t1
slt $t1,$s2,$s3
beq $t1,$0,change
addi $t0,$t0,1
move $s1,$s2
j for
change:
move $s3,$s2
addi $t0,$t0,1
move $s1,$s2
j for
endfor:
slt $t1,$0,$s3
beq $t1,$0,print
move $a0,$s3
li $v0,1
syscall
print:
li $a0,0
li $v0,1
syscall
